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

mmaximum Messages postés 38 Date d'inscription jeudi 13 mars 2008 Statut Membre Dernière intervention 9 décembre 2011 - 7 déc. 2011 à 18:20
cptpingu Messages postés 3835 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 1 novembre 2022 - 9 déc. 2011 à 18:26
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

5 réponses

cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 367
8 déc. 2011 à 08:07
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.
0
cptpingu Messages postés 3835 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 1 novembre 2022 124
8 déc. 2011 à 10:07
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
0
JulSoft Messages postés 354 Date d'inscription dimanche 3 juin 2001 Statut Membre Dernière intervention 11 mars 2013
8 déc. 2011 à 20:34
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.
0
mmaximum Messages postés 38 Date d'inscription jeudi 13 mars 2008 Statut Membre Dernière intervention 9 décembre 2011 2
9 déc. 2011 à 18:15
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.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
cptpingu Messages postés 3835 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 1 novembre 2022 124
9 déc. 2011 à 18:26
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
0