parser une expression mathématique, de manière récursive ou itérative ?

Question

Bonjour,

Je suis actuellement en train de programmer un petit CAS, qui devra tourné sur un système très réduit (calculatrice).
J'ai déjà crée toute la partie pour les structures de données pour l'arbre.
Pour faire simple, chaque opération, fonctions... est un nœud. Certains nœuds peuvent avoir des enfants(opérations, fonctions...), d'autres non (constantes, variables...).

Mon problème maintenant, c'est la construction de l'arbre, et donc le parser d'expression mathématique.
J'avais commencé à écrire un modèle récursif, mais sur certains forums, j'ai vu que ce n'était pas l'optimal.

Donc, je voulais savoir comment on fait pour parser une expression mathématique de manière itérative, et non récursive, et si les gains au niveau de la pile valais le coup.

Aussi, quel est le meilleur modèle/la meilleur technique, pour pouvoir par la suite implémenter de nouvelles fonctions le plus simplement possible ?

Merci d'avance, mmaximum

cs_Julien39 · Answer

Bonjour,

Franchement, pour une expression mathématique, tu peux utiliser la récursivité sans problème. J'ai fait la même chose en java il y a quelques temps et la récursivité ne pose aucun problème.

cptpingu · Answer

Julien39 a raison, il n'y a aucun problème avec la récursivité. Itératif et récursif sont deux méthodes qui se valent toutes les deux. Choisi celle avec laquelle tu es le plus à l'aise. Avant de faire exploser ta pile, tu as quand même de la marge, je te conseil de ne pas trop te prendre la tête la dessus.

Aussi, quel est le meilleur modèle/la meilleur technique, pour pouvoir par la suite implémenter de nouvelles fonctions le plus simplement possible ? 
La meilleur technique est celle du lexer-parser. Après tout une expression mathématique se représente facilement en expression BNF. Tu peux construire un AST (arbre de syntaxe abstrait). C'est la technique utilisée pour faire des compilateurs, évaluateurs, etc... Donc c'est extrêmement extensible. Néanmoins, ce n'est pas la technique la plus facile.
Tu as un exemple de construction d'un AST (avec une image) dans une de mes sources: http://www.cppfrance.com/codes/COMPILATEUR-PSEUDO-PASCAL_49318.aspx

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

JulSoft · Answer

Néanmoins, ce n'est pas la technique la plus facile. 

Oui et non... Je pensais effectivement que créer un lexer + parser ( + interpreteur, il faut quand même faire le calcul une fois, sinon quel intérêt?) était ultra compliqué...

J'ai eu un cours de compilation l'année passée, et je me suis rendu compte que c'est pas si tordu que ça...

Il faut juste un peu de rigueur.

En gros: 
0) (pas obligatoire, pour des maths simples on doit pouvoir faire sans même s' ça peut VRAIMENT aider) Ecrire ta gramaire (BNF / EBNF): les règles de constructions de ton opération
1) faire un lexer qui découpe ta chaine en entrée en morceaux que tu peux reconnaitre (nombres, fonctions, operateurs, paranthèses, ...) qui définissent ta structure. C'est le plus compliqué.
2) Construire ton arbre. On l'avait fair de façon récurssive, c'est le plus simple à mon avis. Même en parsant un langage complet (du J0), on avait pas fait exploser la pile, t'as de la marge.
3) interpréter ton arbre. Là aussi, le plus simple est clairement le récurssif.

mmaximum · Answer

Merci pour vos réponses.
Mais, quand vous parlez de créer un lexer-parser, vous me conseillez plutôt d'utiliser un truc du genre flex/bison, ou de créer mon propre lexer-parser ?
En effet, je crains que le système de lexer-parser soit trop lourd pour être supporté par une calculatrice (64Ko de ram, et l'exécutable ne doit pas être trop gros non plus (max 200Ko)).

Sinon, je pensais utiliser une syntaxe très simple, pour pouvoir être interprétée  facilement.
Par exemple : 3a+#sin(x)
On met des # devant les fonctions, et les variables ne peuvent faire qu'un seul caractère.

cptpingu · Answer

On met des # devant les fonctions, et les variables ne peuvent faire qu'un seul caractère.
Ça ne rend pas les choses forcément plus simples. Avec un bon lexer-parser tu es tranquille pour tout. Pas besoin de ce genre de bidouille.

vous me conseillez plutôt d'utiliser un truc du genre flex/bison, ou de créer mon propre lexer-parser ?
On parle bien de créer son propre lexer-parser.

je crains que le système de lexer-parser soit trop lourd pour être supporté par une calculatrice
C'est pas très lourd un lexer-parser, si bien fait. Tu peux mélanger lexer et parser, et ne pas construire d'arbre de syntaxe, vu que ta grammaire est très simple au final. Tu évalues au fur et à mesure (dès que tu as un noeud complet) en récursif.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

Parser une expression mathématique, de manière récursive ou itérative ?

5 réponses

Votre réponse

Discussions similaires