Stratégies pour simplifier des expressions mathématiques

Question

J'ai bien formée arbre qui représente une expression mathématique. Par exemple, pour la chaîne: "1+2-3*4/5", cela devient analysé dans:

subtract(add(1,2),divide(multiply(3,4),5))

Ce qui est exprimé comme cet arbre:

Ce que je voudrais être en mesure de faire est de prendre cet arbre et de le réduire autant que possible. Dans le cas ci-dessus, c'est assez simple, parce que tous les chiffres sont des constantes. Cependant, les choses commencent à obtenir plus délicat une fois que j'permettre d'inconnues (notée avec un $ suivie de l'identifiant):

"3*$a/$a" devient divide(multiply(3,$a), $a)

Cela devrait simplifier à l' 3, depuis l' $a conditions devraient annuler les uns les autres. La question est: "comment puis-je reconnaître ce d'une manière générique?" Comment puis-je reconnaître que min(3, sin($x)) toujours sin($x)? Comment puis-je reconnaître que sqrt(pow($a, 2)) est abs($a)? Comment puis-je reconnaître que nthroot(pow(42, $a), $a) (le^th de la racine de 42 à l'un^th d'électricité) est 42?

Je me rends compte que cette question est assez large, mais j'ai été me frappant la tête contre ce pour un certain temps et je n'ai pas trouver quelque chose de suffisamment satisfaisant.

Answer 1

Vous voulez sans doute de mettre en œuvre un système de réécriture de termes. Concernant le sous-jacent de mathématiques, ont un oeil à WikiPedia.

Structure d'un terme de module de réécriture d'

Depuis que j'ai mis en œuvre une solution récemment...

• Tout d'abord, préparer une classe CExpression, qui modélise la structure de votre expression.

• Mettre en oeuvre CRule, qui contient un modèle et un remplaçant. Utiliser des symboles spéciaux comme modèle les variables, qui doivent se limite au cours de la correspondance de motif et remplacé dans le remplacement de l'expression.

• Ensuite, mettre en œuvre une classe CRule. C'est la principale méthode applyRule(CExpression, CRule) tente d'adapter la règle à l'encontre de toute loi sous-expression de l'expression. En cas de correspondance, de retourner le résultat.

• Enfin, mettre en œuvre une classe CRuleSet, ce qui est tout simplement un ensemble de CRule objets. La principale méthode reduce(CExpression) s'applique à l'ensemble de règles aussi longtemps que pas plus de règles peuvent être appliquées, puis renvoie la réduction de l'expression.

• En outre, vous avez besoin d'une classe CBindingEnvironment, qui correspond déjà appariés à des symboles pour les paires de valeurs.

Essayer de réécrire l'expression d'une forme normale

N'oubliez pas, que cette approche fonctionne jusqu'à un certain point, mais est susceptible d'être non complet. Cela est dû au fait, que toutes les règles suivantes locale terme réécrit.

Pour faire de ce local de réécriture logique du plus fort, on doit essayer de transformer des expressions dans quelque chose que j'appellerais une forme normale. C'est mon approche:

• Si un terme contient des valeurs littérales, essayez de déplacer le terme le plus à droite possible.

• Finalement, cette valeur littérale peut apparaître plus à droite et qui peut être évalué dans le cadre d'une expression littérale.

Lorsque pour évaluer pleinement l'expression littérale

Une question intéressante est de savoir quand pour évaluer pleinement l'expression littérale. Supposons que vous avez une expression

   x * ( 1 / 3 )

ce qui permettrait de réduire à

   x * 0.333333333333333333

Supposons maintenant que x est remplacé par 3. Cela donnerait quelque chose comme

   0.999999999999999999999999

Ainsi, désireux d'évaluation des rendements légèrement valeur incorrecte.

De l'autre côté, si vous gardez ( 1 / 3 ) et la première remplacer x par 3

   3 * ( 1 / 3 )

une règle de réécriture donnerait

   1

Ainsi, il pourrait être utile d'évaluer pleinement l'expression littérale de retard.

Exemples de règles de réécriture

Voici comment mes règles apparaissent à l'intérieur de l'application: la _1, _2, ... symboles correspondent à aucune sous-expression:

addRule( new TARuleFromString( '0+_1',   // left hand side  :: pattern
                               '_1'      // right hand side :: replacement
                             ) 
       );

ou un peu plus compliqué

addRule( new TARuleFromString( '_1+_2*_1', 
                               '(1+_2)*_1' 
                             ) 
       );

Certains symboles spéciaux seul match spécial des sous-expressions. E. g. _Literal1, _Literal2, ... correspondent uniquement des valeurs littérales:

addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 
                               'exp( _Literal1 + _Literal2 )' 
                             ) 
       );

Cette règle se déplace non-expression littérale de la gauche:

addRule( new TARuleFromString( '_Literal*_NonLiteral', 
                               '_NonLiteral*_Literal' 
                             ) 
       );

N'importe quel nom, qui commence par un '_', est un modèle de variable. Alors que le système correspond à une règle, il maintient une pile de devoirs de déjà appariés symboles.

Enfin, n'oubliez pas que les règles peuvent produire non la résiliation de remplacement des séquences. Ainsi, alors que la réduction de l'expression, de rendre le processus rappelez-vous, laquelle des expressions intermédiaires ont déjà été atteint auparavant.

Dans mon application, je ne sauve pas des expressions intermédiaires directement. Je garde un tableau de MD5() hachages d'expression intermédiaire.

Un ensemble de règles, comme un point de départ

Voici un ensemble de règles pour commencer:

            addRule( new TARuleFromString( '0+_1', '_1' ) );
            addRule( new TARuleFromString( '_Literal2=0-_1', '_1=0-_Literal2' ) );
            addRule( new TARuleFromString( '_1+0', '_1' ) );

            addRule( new TARuleFromString( '1*_1', '_1' ) );
            addRule( new TARuleFromString( '_1*1', '_1' ) );

            addRule( new TARuleFromString( '_1+_1', '2*_1' ) );

            addRule( new TARuleFromString( '_1-_1', '0' ) );
            addRule( new TARuleFromString( '_1/_1', '1' ) );

            // Rate = (pow((EndValue / BeginValue), (1 / (EndYear - BeginYear)))-1) * 100 

            addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 'exp( _Literal1 + _Literal2 )' ) );
            addRule( new TARuleFromString( 'exp( 0 )', '1' ) );

            addRule( new TARuleFromString( 'pow(_Literal1,_1) * pow(_Literal2,_1)', 'pow(_Literal1 * _Literal2,_1)' ) );
            addRule( new TARuleFromString( 'pow( _1, 0 )', '1' ) );
            addRule( new TARuleFromString( 'pow( _1, 1 )', '_1' ) );
            addRule( new TARuleFromString( 'pow( _1, -1 )', '1/_1' ) );
            addRule( new TARuleFromString( 'pow( pow( _1, _Literal1 ), _Literal2 )', 'pow( _1, _Literal1 * _Literal2 )' ) );

//          addRule( new TARuleFromString( 'pow( _Literal1, _1 )', 'ln(_1) / ln(_Literal1)' ) );
            addRule( new TARuleFromString( '_literal1 = pow( _Literal2, _1 )', '_1 = ln(_literal1) / ln(_Literal2)' ) );
            addRule( new TARuleFromString( 'pow( _Literal2, _1 ) = _literal1 ', '_1 = ln(_literal1) / ln(_Literal2)' ) );

            addRule( new TARuleFromString( 'pow( _1, _Literal2 ) = _literal1 ', 'pow( _literal1, 1 / _Literal2 ) = _1' ) );

            addRule( new TARuleFromString( 'pow( 1, _1 )', '1' ) );

            addRule( new TARuleFromString( '_1 * _1 = _literal', '_1 = sqrt( _literal )' ) );

            addRule( new TARuleFromString( 'sqrt( _literal * _1 )', 'sqrt( _literal ) * sqrt( _1 )' ) );

            addRule( new TARuleFromString( 'ln( _Literal1 * _2 )', 'ln( _Literal1 ) + ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 * _Literal2 )', 'ln( _Literal2 ) + ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 * _2 )', 'log2( _Literal1 ) + log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 * _Literal2 )', 'log2( _Literal2 ) + log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 * _2 )', 'log10( _Literal1 ) + log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 * _Literal2 )', 'log10( _Literal2 ) + log10( _1 )' ) );

            addRule( new TARuleFromString( 'ln( _Literal1 / _2 )', 'ln( _Literal1 ) - ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 / _Literal2 )', 'ln( _Literal2 ) - ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 / _2 )', 'log2( _Literal1 ) - log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 / _Literal2 )', 'log2( _Literal2 ) - log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 / _2 )', 'log10( _Literal1 ) - log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 / _Literal2 )', 'log10( _Literal2 ) - log10( _1 )' ) );


            addRule( new TARuleFromString( '_Literal1 = _NonLiteral + _Literal2', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral * _Literal2', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral / _Literal2', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 =_NonLiteral - _Literal2',  '_Literal1 + _Literal2 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_NonLiteral + _Literal2 = _Literal1 ', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral * _Literal2 = _Literal1 ', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral / _Literal2 = _Literal1 ', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1',  '_Literal1 + _Literal2 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1 ', '_Literal1 + _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal2 - _NonLiteral = _Literal1 ', '_Literal2 - _Literal1 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_Literal1 = sin( _NonLiteral )', 'asin( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = cos( _NonLiteral )', 'acos( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = tan( _NonLiteral )', 'atan( _Literal1 ) = _NonLiteral' ) );

            addRule( new TARuleFromString( '_Literal1 = ln( _1 )', 'exp( _Literal1 ) = _1' ) );
            addRule( new TARuleFromString( 'ln( _1 ) = _Literal1', 'exp( _Literal1 ) = _1' ) );

            addRule( new TARuleFromString( '_Literal1 = _NonLiteral', '_NonLiteral = _Literal1' ) );

            addRule( new TARuleFromString( '( _Literal1 / _2 ) = _Literal2', '_Literal1 / _Literal2 = _2 ' ) );

            addRule( new TARuleFromString( '_Literal*_NonLiteral', '_NonLiteral*_Literal' ) );
            addRule( new TARuleFromString( '_Literal+_NonLiteral', '_NonLiteral+_Literal' ) );

            addRule( new TARuleFromString( '_Literal1+(_Literal2+_NonLiteral)', '_NonLiteral+(_Literal1+_Literal2)' ) );
            addRule( new TARuleFromString( '_Literal1+(_Literal2+_1)', '_1+(_Literal1+_Literal2)' ) );

            addRule( new TARuleFromString( '(_1*_2)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_2*_1)+(_2*_3)', '(_1+_3)*_2' ) );

            addRule( new TARuleFromString( '(_2*_1)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_1*_2)+(_2*_3)', '(_1+_3)*_2' ) );

            addRule( new TARuleFromString( '(_Literal * _1 ) / _Literal', '_1' ) );
            addRule( new TARuleFromString( '(_Literal1 * _1 ) / _Literal2', '(_Literal1 * _Literal2 ) / _1' ) );

            addRule( new TARuleFromString( '(_1+_2)+_3', '_1+(_2+_3)' ) );
            addRule( new TARuleFromString( '(_1*_2)*_3', '_1*(_2*_3)' ) );

            addRule( new TARuleFromString( '_1+(_1+_2)', '(2*_1)+_2' ) );

            addRule( new TARuleFromString( '_1+_2*_1', '(1+_2)*_1' ) );

            addRule( new TARuleFromString( '_literal1 * _NonLiteral = _literal2', '_literal2 / _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 + _NonLiteral = _literal2', '_literal2 - _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 - _NonLiteral = _literal2', '_literal1 - _literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 / _NonLiteral = _literal2', '_literal1 * _literal2 = _NonLiteral' ) );

Établir des règles de première classe expressions

Un point intéressant: Depuis les règles ci-dessus sont expression particulière, qui obtiennent les évaluer correctement par l'analyseur d'expression, les utilisateurs peuvent même ajouter de nouvelles règles et de renforcer ainsi la demande de capacités de réécriture.

L'analyse des expressions (ou plus général: les langues)

Pour le Cacao/OBjC applications, Dave DeLong est DDMathParser est un candidat parfait pour un point de vue syntaxique analyser des expressions mathématiques.

Pour les autres langues, nos vieux amis de Lex & Yacc ou la plus récente GNU Bison peut être de l'aide.

Beaucoup plus jeune et avec un énorme ensemble de prêts à utiliser la syntaxe des fichiers, ANTLR est un moderne analyseur générateur basé sur Java. D'ailleurs purement utilisation en ligne de commande, ANTLRWorks fournit une autre interface pour construire et déboguer ANTLR en fonction des analyseurs. ANTLR génère des grammaires pour les différents hôtes de la langue, comme JAVA, C, Python, PHP ou C#. Le code ActionScript runtime est actuellement cassé.

Dans le cas où vous souhaitez apprendre comment analyser les expressions (ou les langues en général) à partir du bas, je vous propose ce livre gratuit de texte à partir de Niklaus Wirth (ou de l' allemand de l'édition), le célèbre inventeur de Pascal et Modula-2.

Answer 2

Cette tâche peut devenir très compliqué (en plus de la simple transformation). Essentiellement, c'est ce que l'algèbre logiciel fait tout le temps.

Vous pouvez trouver un lisible introduction comment cela est fait (à base de règles d'évaluation), par exemple pour Mathematica.

Answer 3

Vous êtes désireux de construire un CAS (calcul de l'algèbre système) et le sujet est tellement vaste qu'il y a tout un champ d'étude qui lui est dédié. Ce qui signifie qu'il y a quelques livres qui sera probablement la réponse à votre question mieux que SI.

Je sais que certains systèmes de construire des arbres qui permettent de réduire les constantes d'abord et ensuite mettre l'arbre dans une forme normalisée et ensuite utiliser une grande base de données de prouvé/formules connues pour transformer le problème en une autre forme.

Answer 4

Je crois que vous avez de "force brute" de tels arbres.

Vous aurez à formuler un couple de règles qui décrivent les possibilités de simplification. Ensuite, vous habe à marcher à travers les arbres et la recherche de règles applicables. Depuis quelques simplifications pourraient conduire à des résultats plus simples que d'autres, vous aurez à faire quelque chose de similaire que vous faites pour trouver le chemin le plus court sur un plan de métro: essayer toutes les possibilités et de trier les résultats selon certains critères de qualité.

Depuis, le nombre de ces scénarios est finie, vous pourriez être en mesure de découvrir la simplification des règles automatiquement en essayant toutes les combinaisons d'opérateurs et variables et encore une fois, un algorithme génétique, qui vérifie que la règle n'a pas été trouvé avant et qu'en fait, il simplifie l'entrée.

Multiplications peuvent être représentés comme des ajouts, de sorte que d'une règle peut être que l'un annule de lui-même: 2a-un = un+un-un

Une autre règle serait d'abord de se multiplier hors de toutes les divisions, parce que ce sont des fractions. Exemple:

1/2 + 3/4 Découvrez toutes les divisions et ensuite multiplier chaque fraction dont le dénominateur de l'expression sur les deux côtés de toutes les autres fractions

4/8 + 6/8 Ensuite, tous les éléments ont le même dénominateur et donc peut unifiée pour (4+6)/8 = 10/8

Enfin vous trouver le plus grand commun diviseur entre le haut et le bas 5/4

Appliqué à votre arbre, la stratégie serait de travailler à partir des feuilles du bas vers le haut, la simplification de chaque multiplication d'abord par la conversion à des ajouts. Alors simplifier l'ajout de chaque comme les fractions

Tout le temps que vous devriez vérifier à nouveau votre raccourci règles de découvrir un tel simplifcations. À savoir qu'une règle s'applique, vous devez probablement soit d'essayer toutes les permutations d'un sous-arbre. E. g. La une-une règle s'appliquerait également pour un+un. Il pourrait y avoir un a+b-a.

Juste quelques pensées, de l'espérance qui vous donne quelques idées...

Answer 5

Vous ne pouvez pas en général le faire parce que, bien qu'ils soient de la même mathématiquement, il pourrait ne pas être la même dans l'arithmétique des ordinateurs. Par exemple, -MAX_INT est pas défini, donc --%a =/= %une. De même, pour les flotteurs, vous avez à traiter avec NaN et Inf de façon appropriée.