Expression d'écriture: Infix, Postfix et Prefix

Question

Ma tâche consiste à écrire une application (malheureusement sur C) qui lit l'expression en notation infixe (avec des opérateurs variables, unaires et binaires) et la stocke en mémoire, puis l'évalue. En outre, des vérifications d’exactitude doivent être effectuées.

par exemple:

  

3 * (A + B) - (- 2-78) * 2 + (0 * A)

Après avoir obtenu toutes les valeurs, le programme devrait le calculer.

La question est: Quelle est la meilleure façon de procéder? (Avec optimisation et validation)

Quelle notation choisir comme base d’arbre?

Dois-je représenter l'expression en tant qu'arbre? Si c'est le cas, je peux facilement l'optimiser (il suffit de supprimer les nœuds qui renvoient 0 ou moins).

A bientôt,

Answer 1

Le lien suggéré dans le commentaire de Greg Hewgill ci-dessus contient toutes les informations dont vous aurez besoin:

Si vous insistez pour écrire le vôtre,

• un un analyseur récursif de descente est probablement le moyen le plus simple de le faire à la main.
• Sinon, vous pourriez utiliser un outil comme Bison (puisque vous travaillez en C). Ce tutoriel est le meilleur que j'ai vu pour travailler avec Flex et Bison (ou Lex / Yacc)

Vous pouvez également rechercher "évaluateur d'expression" & <; a > sur Codeproject - ils ont beaucoup d'articles sur le sujet.

Je suis tombé sur l'évaluateur d'expression du programme M4 il y a quelque temps. Vous pouvez étudier son code pour voir comment cela fonctionne. Je pense ce lien sur Google Codesearch est la version que j'ai vue.

Answer 2

Votre question suggère que votre solution est conforme aux exigences:

  

malheureusement sur C

il est donc possible que certaines suggestions ne soient pas autorisées. Néanmoins, je dirais que c'est un problème assez compliqué à résoudre et que vous seriez mieux mieux d'essayer de trouver une bibliothèque existante appropriée que vous pouvez relier à votre code C pour le faire à votre place. . Cela réduirait probablement le temps et les efforts requis pour faire fonctionner le code, ainsi que les efforts de maintenance en cours. Bien sûr, vous devrez penser à l’octroi de licence, mais je serais surpris de ne pas disposer d’une bonne bibliothèque d’analyses / évaluations "disponible". qui pourrait faire un bon travail de cela.