Stratégies pour simplifier les expressions mathématiques

j'ai un arbre bien formé qui représente une expression mathématique. Par exemple, étant donné la chaîne de caractères: "1+2-3*4/5" , ceci est divisé en: 

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

qui est exprimé comme cet arbre:

"1+2-3*4/5"

ce que j'aimerais pouvoir faire, c'est prendre cet arbre et 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 à devenir plus compliquées une fois que j'ai pris en compte les inconnues (indiquées par un $ suivi d'un identifiant):

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

cela devrait simplifier à 3 , puisque les Termes $a devraient s'annuler mutuellement. 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)) est toujours sin($x) ? Comment puis-je reconnaître que sqrt(pow($a, 2)) c'est abs($a) ? Comment puis-je reconnaître que nthroot(pow(42, $a), $a) (la racine th de 42 à la TH puissance) est 42 ?

je me rends compte que cette question est assez large, mais je me bats la tête contre cela depuis un moment et je n'ai rien trouvé d'assez satisfaisant.

59
demandé sur Dave DeLong 2011-09-24 20:23:33

6 réponses

vous voulez probablement implémenter un term rewriting system . En ce qui concerne les mathématiques sous-jacentes, jetez un oeil à WikiPedia .

Structure d'un terme module de réécriture

depuis que j'ai mis en place une solution récemment...

  • tout d'abord, préparez une expression de Classe C, qui modèle la structure de votre expression.

  • Implement CRule , qui contient un motif et un remplacement. Utilisez des symboles spéciaux comme variables de pattern, qui doivent être liées lors de la correspondance de pattern et remplacées dans l'expression de remplacement.

  • ensuite, mettre en œuvre une classe CRule . C'est la méthode principale applyRule(CExpression, CRule) qui essaie de faire correspondre la règle à n'importe quelle sous-expression d'expression applicable. En cas de correspondance, le retour résultat.

  • Enfin, de mettre en œuvre une classe CRuleSet , qui est simplement un ensemble de CRule objets. La méthode principale reduce(CExpression) applique l'ensemble de règles aussi longtemps qu'aucune autre règle ne peut être appliquée et retourne ensuite l'expression réduite.

  • en outre, vous avez besoin d'une classe CBindingEnvironment , qui correspond aux symboles déjà assortis aux valeurs correspondantes.

essayer de réécrire l'expression à 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 renforcer cette logique de réécriture locale, on devrait essayer de transformer les expressions en 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 la plus à droite et peut être évaluée comme faisant partie d'une expression entièrement littérale.

quand évaluer l'expression

une question intéressante est de savoir quand évaluer complètement littéral expression. Supposons que vous ayez une expression 

   x * ( 1 / 3 )

qui passerait à 

   x * 0.333333333333333333

supposons maintenant que x soit remplacé par 3. Cela donnerait quelque chose comme 

   0.999999999999999999999999

ainsi l'évaluation impatiente renvoie une valeur légèrement incorrecte.

de l'autre côté, si vous gardez ( 1 / 3 ) et remplacez d'abord x par 3 

   3 * ( 1 / 3 )

une règle de réécriture donnerait 

   1

ainsi, il pourrait être utile d'évaluer l'expression littérale tardive.

exemples de règles de réécriture

Voici comment mes règles apparaissent à l'intérieur de l'application: le _1, _2, ... les symboles correspondent à n'importe quelle 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 ne correspondent qu'à des sous-expressions spéciales. Par exemple: _Literal1, _Literal2,... match seulement des valeurs littérales: 

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

cette règle déplace l'expression non littérale à gauche: 

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

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

enfin, n'oubliez pas que les règles peuvent donner des séquences de remplacement sans fin. Ainsi, tout en réduisant l'expression, faire le processus se souviennent, quelles expressions intermédiaires ont déjà été atteints auparavant.

dans mon implémentation, Je ne sauvegarde pas directement les expressions intermédiaires. Je garde un tableau de hachages MD5() 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: puisque les règles ci-dessus sont des expressions spéciales, qui sont correctement évaluées par l'analyseur d'expressions, les utilisateurs peuvent même ajouter de nouvelles règles et ainsi améliorer les capacités de réécriture de l'application.

Analyse des expressions (ou plus général: les langues)

For Cocoa / OBjC applications , Dave Delong's DDMathParser est un candidat parfait pour l'analyse syntaxique des expressions mathématiques.

pour les autres langues, nos vieux amis Lex & Yacc ou le plus récent GNU Bison pourrait être utile.

beaucoup plus jeune et avec un enourmous ensemble de prêt à utiliser la syntaxe-fichiers , ANTLR est un générateur de parser moderne basé sur Java. D'ailleurs purement utilisation en ligne de commande, ANTLRWorks fournit un frontend GUI pour construire et déboguer ANTLR en fonction des analyseurs. ANTLR génère des grammaires pour diverses langues hôtes , comme JAVA, C, Python, PHP ou C# . L'exécution ActionScript est actuellement cassée .

dans le cas où vous souhaitez apprendre à analyser les expressions (ou les langues en général) de la de bas en haut, je proposerais ce texte de livre gratuit de Niklaus Wirth (ou le édition de livre allemande ), le célèbre inventeur de Pascal et Modula-2.

78
répondu SteAp 2017-05-23 12:26:01

cette tâche peut devenir assez compliquée (en dehors de la transformation la plus simple). Essentiellement, c'est ce que logiciel d'algèbre fait tout le temps.

vous pouvez trouver une introduction lisible comment ceci est fait (évaluation basée sur des règles) par exemple pour Mathematica .

10
répondu Howard 2011-09-24 16:35:15

vous voulez construire un CAS (calcul système d'algèbre) et le sujet est si large qu'il ya un domaine d'étude entier qui lui est dédié. Ce qui veut dire qu'il y a quelques livres qui répondront probablement mieux à votre question.

je sais que certains systèmes construisent des arbres qui réduisent les constantes d'abord, puis mettent l'arbre dans une forme normalisée, puis utilisent une grande base de données de formules prouvées/connues pour transformer le problème dans une autre forme.

7
répondu Andrew White 2011-09-24 16:41:41

je crois que vous devez "forcer" de tels arbres.

vous devrez formuler quelques règles qui décrivent les simplifications possibles. Ensuite, vous devez parcourir l'arbre et chercher les règles applicables. Puisque certaines simplifications peuvent conduire à des résultats plus simples que d'autres, vous aurez à faire une chose similaire que vous faites pour trouver le trajet le plus court sur un plan de métro: essayer toutes les possibilités et trier les résultats par certains critères de qualité.

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

les Multiplications peuvent être représentées comme des additions, de sorte qu'une règle pourrait être que a-A s'annule: 2a-A = A+A-a

un autre la règle serait d'abord de multiplier toutes les divisions parce que ce sont des fractions. Exemple:

1/2 + 3/4 Découvrir toutes les divisions et ensuite multiplier chaque fraction avec le diviseur des deux côtés de toutes les autres fractions

4/8 + 6/8 Alors tous les éléments ont le même diviseur et ainsi peut l'unifié à (4+6)/8 = 10/8

enfin vous trouvez le diviseur commun le plus élevé 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 en simplifiant chaque multiplication d'abord en la convertissant en additions. Puis en simplifiant chaque addition comme les fractions

pendant tout ce temps, vous vérifiez vos règles de raccourci pour découvrir de telles simplifications. À savoir qu'une règle s'applique, vous devez probablement soit d'essayer toutes les permutations d'un sous-arbre. Par exemple: La règle a-a s'appliquerait également pour A+a. Il pourrait y avoir un a+b-a.

juste quelques pensées espère que vous donne quelques idées...

1
répondu Cocoanetics 2011-09-24 17:44:30

vous ne pouvez en fait pas en général faire cela parce que, bien qu'ils soient les mêmes mathématiquement, les mai ne sont pas les mêmes en arithmétique informatique. Par exemple, - MAX_INT n'est pas défini, donc --%a =/= %a. De même, pour les flotteurs, vous devez traiter avec NaN et Inf de façon appropriée.

0
répondu Joel 2011-09-24 16:35:54

mon approche naïve serait d'avoir une sorte de structure de données avec des inverses de chaque fonction (i.e. divide et multiply ). Vous auriez évidemment besoin de plus de logique pour s'assurer qu'ils sont en fait inverse puisque multiplier par 3 et ensuite diviser par 4 n'est pas en fait un inverse.

bien que cela soit primitif, je pense que c'est une première passe décente au problème et résoudrait beaucoup de cas que vous avez noté dans votre question.

je ne hâte de voir votre solution complète et regarder dans la crainte à l'est mathématique, de la brillance :)

0
répondu Sam Soffes 2011-09-24 17:29:03