Conception intelligente d'un analyseur mathématique?

Question

Quel est le moyen le plus intelligent de concevoir un analyseur mathématique? Ce que je veux dire est une fonction qui prend une chaîne mathématique (telle que: "2 + 3/2 + (2 * 5)") et renvoie la valeur calculée. J'en ai écrit un en VB6 il y a bien longtemps, mais il s'est avéré être trop volumineux et pas très portable (ou intelligent en l'occurrence ...). Les idées générales, le code pseudo ou le code réel sont appréciés.

Answer 1

Une très bonne approche impliquerait deux étapes. La première étape consiste à convertir l'expression d'infix en postfix (par exemple via la notation du parc de triage de Dijkstra . Une fois que c'est fait, il est assez facile d'écrire un évaluateur postfix .

Answer 2

J'ai écrit quelques articles de blog sur la conception d'un analyseur mathématique. Il existe une introduction , des connaissances de base sur grammaires , exemple d'implémentation écrit en Ruby et un suite de tests . Peut-être trouverez-vous ces informations utiles.

Answer 3

Vous avez plusieurs approches. Vous pouvez générer du code dynamique et l'exécuter afin d'obtenir la réponse sans avoir à écrire beaucoup de code. Il suffit d’effectuer une recherche sur le code généré par le moteur d’exécution dans .NET. De nombreux exemples sont disponibles.

Vous pouvez également créer un analyseur et générer un petit arbre d’analyse qui sera ensuite utilisé pour évaluer l’expression. Encore une fois, c'est assez simple pour les expressions de base. Vérifiez codeplex car je crois qu’ils ont un analyseur mathématique. Ou tout simplement regarder BNF qui inclura des exemples. Tout site Web présentant des concepts de compilateur l'inclura comme exemple de base.

évaluateur d'expressions Codeplex

Answer 4

Je sais que c'est vieux, mais je suis tombé sur cette tentative d'essayer de développer une calculatrice dans le cadre d'une application plus grande et j'ai rencontré quelques problèmes en utilisant la réponse acceptée. Les liens étaient extrêmement utiles pour comprendre et résoudre ce problème et ne devaient pas être négligés. J'écrivais une application Android en Java et pour chaque élément de l'expression "chaîne". En fait, j'ai stocké une chaîne dans une liste de tableaux lorsque l'utilisateur tape sur le clavier. Pour la conversion d'infixe en postfixe, j'ai itéré dans chaque chaîne de la liste de tableaux, puis j'ai évalué la liste de tableaux nouvellement arrangée, ArrayList. C'était fantastique pour un petit nombre d'opérandes / opérateurs, mais les calculs les plus longs étaient systématiquement arrêtés, en particulier lorsque les expressions commençaient à être évaluées en non-entiers. Dans le lien fourni pour la conversion de Infixe à Postfix , il suggère de faire apparaître la pile si l'élément numérisé est un opérateur et que l'élément topStack a une priorité plus élevée. J'ai trouvé que c'est presque correct. Si vous avez sauté l’élément topStack si sa priorité est plus grande, OU ÉGAL à l’opérateur scanné, vos calculs sont finalement corrects. J'espère que cela aidera tous ceux qui travaillent sur ce problème, et merci à Justin Poliey (et fas?) Pour avoir fourni des liens inestimables.

Answer 5

Si vous avez un " toujours actif " application, il suffit de poster la chaîne mathématique pour google et d’analyser le résultat. C'est simple, mais je ne sais pas si c'est ce dont vous avez besoin, mais je suppose que c'est intelligent.

Answer 6

La question connexe l'analyseur d'équation (expression) avec priorité? contient quelques informations utiles. sur la façon de commencer avec cela aussi.

-Adam

Answer 7

En supposant que votre entrée soit une expression infixe au format chaîne, vous pouvez la convertir en postfix . et, en utilisant une paire de piles: une pile d'opérateur et une pile d'opérandes, travaillez la solution à partir de là. Vous pouvez trouver des informations générales sur les algorithmes sur le lien Wikipedia.

Answer 8

ANTLR est un très bon générateur d’analyseur LL (*). Je le recommande vivement.

Answer 9

Les développeurs souhaitent toujours adopter une approche propre et essaient de mettre en oeuvre la logique d'analyse syntaxique à partir de zéro, aboutissant généralement à la Algorithme de pontage de Dijkstra . Le résultat est un code soigné, mais éventuellement bogué. J'ai développé une telle API, JMEP , qui fait tout cela, mais il m'a fallu des années pour avoir un code stable.

Même avec tout ce travail, vous voyez même sur cette page du projet que je songe sérieusement à passer à JavaCC ou à ANTLR, même après tout ce travail déjà accompli.

Answer 10

Onze ans d’avenir à partir de la date à laquelle cette question a été posée: si vous ne voulez pas réinventer la roue, il existe de nombreux analyseurs syntaxiques mathématiques exotiques.

Il y en a un que j’ai écrit il ya des années et qui prend en charge les opérations arithmétiques, la résolution d’équations, le calcul différentiel, le calcul intégral, les statistiques de base, la définition de fonctions / formules, la représentation graphique, etc.

Il est appelé ParserNG et gratuitement.

L'évaluation d'une expression est aussi simple que:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

Ou en utilisant des variables et en calculant des expressions simples:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

Ou en utilisant les fonctions:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

Ou pour évaluer la dérivée en un point donné (notez qu’elle fait une différenciation symbolique (non numérique) en coulisse, de sorte que la précision ne soit pas limitée par les erreurs des approximations numériques):

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Ce qui différencie x ^ 3 * ln (x) une fois à x = 3. Le nombre de fois que vous pouvez différencier est 1 pour l'instant.

ou pour l'intégration numérique:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

Cet analyseur est très rapide et propose de nombreuses autres fonctionnalités.

Les travaux ont été achevés sur le portage sur Swift via des liaisons vers Objective C et nous l'avons utilisé dans la représentation graphique d'applications parmi d'autres cas d'utilisation itératifs.

AVERTISSEMENT: je suis l'auteur de ParserNG.