La conception intelligente d'un analyseur de maths?
Quelle est la façon la plus intelligente de concevoir un analyseur de mathématiques? Ce que je veux dire est une fonction qui prend une chaîne de maths (comme: "2 + 3 / 2 + (2 * 5)") et renvoie la valeur calculée? J'en ai écrit un en VB6 il y a des années mais il a fini par être trop gonflé et pas très portable (ou intelligent d'ailleurs...). Les idées générales, le code psuedo ou le code réel sont appréciés.
9 réponses
une assez bonne approche comporterait deux étapes. La première étape consiste à convertir l'expression de infix en postfix (par exemple via la Cour de triage de Dijkstra ). Une fois que c'est fait, c'est assez banal d'écrire un postfix evaluator .
j'ai écrit quelques billets de blog sur la conception d'un analyseur de mathématiques. Il y a un introduction , connaissances de base sur grammars , mise en oeuvre d'échantillon écrit en Ruby et un suite de test . Peut-être trouverez-vous ces documents utiles.
vous avez quelques approches. Vous pourriez générer dynamiquement du code et de l'exécuter afin d'obtenir la réponse sans avoir besoin d'écrire beaucoup de code. Il suffit d'effectuer une recherche sur le code généré par l'exécution dans .NET et il y a beaucoup d'exemples autour.
vous pouvez aussi créer un analyseur réel et générer un petit arbre qui est ensuite utilisé pour évaluer l'expression. Encore une fois, c'est assez simple pour les expressions de base. Regardez codeplex car je crois qu'ils il y a un analyseur de maths dessus. Ou cherchez simplement BNF qui inclura des exemples. Tout site web présentant des concepts de compilateurs inclura ceci comme exemple de base.
si vous avez une application" toujours sur", postez simplement la chaîne de maths à google et analysez le résultat. Façon Simple mais pas sûr si c'est ce dont vous avez besoin - mais intelligent dans un sens, je suppose.
La question relative à la Équation (expression) de l'analyseur, avec une priorité? a quelques bonnes informations sur la façon d'obtenir commencé.
- Adam
je sais que c'est vieux, mais je suis tombé sur ce en essayant de développer une calculatrice dans le cadre d'une plus grande application et couru sur certains problèmes en utilisant la réponse acceptée. Les liens ont été extrêmement utiles pour comprendre et résoudre ce problème et ne devraient pas être ignorés. J'écrivais une application Android en Java et pour chaque élément de l'expression "string", j'ai en fait stocké une chaîne dans un ArrayList comme les types d'utilisateur sur le clavier. Pour la conversion infix-to-postfix, j'ai itéré à travers chaque chaîne dans L'ArrayList, on a ensuite évalué l'ArrayList de cordes postfix nouvellement disposé. C'était fantastique pour un petit nombre d'opérandes/opérateurs, mais des calculs plus longs étaient constamment désactivés, surtout lorsque les expressions commençaient à être évaluées à des non-entiers. Dans le lien fourni pour la conversion Infix à Postfix , il suggère de casser la pile si l'élément scanné est un opérateur et l'élément topStack a une priorité plus élevée. Je trouve que c'est presque correct. Popping l' topStack item si sa priorité est supérieure ou égale à l'opérateur scanné a finalement fait mes calculs sortent correct. Espérons que cela aidera quiconque travaille sur ce problème, et grâce à Justin Poliey (et fas?) pour avoir fourni des liens précieux.
en supposant que votre entrée est une expression infix au format chaîne, vous pouvez la convertir en postfix et, en utilisant une paire de piles: une pile opérateur et une pile opérande, travailler la solution à partir de là. Vous pouvez trouver des informations générales sur l'algorithme Sur le lien Wikipedia.
ANTLR est un très beau générateur Parser LL (*). Je le recommande fortement.
les développeurs veulent toujours avoir une approche propre, et essayer de mettre en œuvre la logique d'analyse à partir de la base, se terminant généralement avec le algorithme de triage Dijkstra . Le résultat est un code d'apparence soigné, mais peut-être monté avec des bogues. 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 pouvez voir même à partir de cette page de projet que je suis sérieusement envisager de passer à L'utilisation de JavaCC ou ANTLR, même après tout ce travail déjà fait.