Discussion :

[MysticKhal_0]

Bonjour,

J'aimerais écrire une petite calto qui puisse faire des opération de base (+, -, *, /) avec gestion des parenthèses. Voilà le problème c'est que je ne vois pas quel algo pourrait être le plus efficace et le plus simple à coder :s
J'ai lu qu'on pouvait utiliser une stack, convertir l'expression en notation polonaise inversée puis l'évaluer à l'aide d'une stack, mais cette solution est-elle efficace et simple? J'ai aussi lu que l'on pouvait utiliser un arbre (même question, ceci est-il une bonne idée)?

Si quelqu'un pourrait me donner un algo ou un lien traitant du sujet je lui serait vraiment reconnaissant Je cherche avant tout une méthode rapide à coder, pour le reste ça devrait aller ^^'

Merci

[j.p.mignot]

J'ai déjà fait cela en association avec de la reconnaissance d'écriture.
j'ai utilisé
1- notation polonaise inversée.
2- La stack pour gérer les parenthèses { définition des "blocs" (....) et les des entrelacer le cas échéant }
3- des algorithmes de base pour évaluer les fonctions de base
( racine, sin, cos, ...)

L'ensemble tournait sur un processeur à 8M et 12k de mémoire.

Du point de vue des utilisateurs, la notation polonaise inversée à été la plus difficile à appréhender. Pour un produit "grand publique" j'ai donc été amené à réintroduire une entrée "standard" avec la gestion de =. Cela est nettement moins rationnel et devrait , à mon avis, si il n'y a pas de contraintes "client" être évité.

[MysticKhal_0]

Merci pour ta réponse
Par contre la conversion de la notation standard à la notation polonaise inversée n'est pas très dur. Je vais peut être utiliser cette méthode alors à moins qu'il n'y ait quelquechose de plus performant?

[Jean-Marc.Bourguet]

Recherche dans mes derniers messages sur fr.comp.lang.c, j'en ai écrit deux... (news:87u0ajmigu.fsf@news.bourguet.org, news:87lkvvmenj.fsf@news.bourguet.org)

[ToTo13]

Bonjour,
c'est assez simple à programmer, le plus dur est d'avoir une grammaire qui reconnaisse les expressions arithmétiques, mais google est ton ami.
Ensuite, il te suffit de transcrire la grammaire dans le langage de ton choix.

[j.p.mignot]

je dispose aussi d'1 code en delphi et qui inclue la gestion des parenthèses, les fonctions de base ( + * / - trigo, log, puissance, ... )
je pourrais le fournir sur demande.

[Betatesteur]

delphi ou pas je le repasserai en pseudo code. j'aimerai comparer avec ce que je suis en train de faire donc oui je veux bien ton code

[j.p.mignot]

j'envoie le code dans le prochain mail.
Dès que vous l'avez récupéré, dites le moi afin que je le supprime du forum.
cela est un peu long et inutile d'être maintenu en permanence. L’option « fichier attaché » n’est malheureusement pas encore active

[j.p.mignot]

supprimé

[TicTacToe]

Juste pour apporter mon point de vue

J'ai fais un évaluteur il y a un 10aine d'année, c'etait pour la fac, car marre d'avoir des fonctions en dur et recompiler à chaque fois.
Depuis, je l'utilise toujours, pour mes progs et professionellement.

Comment j'ai procédé.

1. Le parsing, determiner chaque elt de la chaine (d'ailleurs je m'étais cassé la tête à l'époque car je tenais absolument à pouvoir ecrire comme sur papier,ie , 2x signifiait bien 2 * x, sinx signifiait bient sin(x) etc...)

2. Chaque elt est d'une certaine nature (nbre/cte, fonction, opérateur, variables) avec une certaine priorité de lecture pour l'établissement de l'arbre.

3. J'ai fais mon stockage de l'expression dans un arbre. Chaque element est un objet (au sens classe) avec une méthode 'Calculer'.

3. La méthode calculer se charge selon sa nature, de prendre ses fils (1 ou plusieurs selon la nature) et de renvoyer fils1.Calculer * fils2.Calculer pour le cas d'une multiplication.
Finalement fils1 pouvait être n'importe quel sous-arbre, le résultat de se sous-arbre était incombé à fils1.

4. Donc chaque feuille de l'arbre est soit une constante soit un nombre, c'est ce qui arrete le parcours de l'arbre.
Le résultat d'un expression est NoeudSommet.Calculer, tout simplement.

C'est pas la méthode la plus rapide, néanmoins j'ai jamais eu de pb de vitesse même avec des expressions compliquée et sur des 486...

De plus, pour le tracer d'une fonction par exemple, le parsing n'est effectué qu'une seule fois. Après, l'arbre est gardé en mémoire et il est autonome. Le calcule est alors très rapide. (uniquement le parcours de l'arbre et les opérations)

Le gros avantage, c'est que une fois l'expression en arbre on peut faire ce que l'on veut sur l'expression en litéral.

J'avais notamment implémenté, en plus de la méthode 'calculer', la méthode 'Deriver' qui permettait de renvoyer un 2eme arbre, résultat dérive de la 1ere expression. Avec l'opération inverse de transfo. de l'arbre en chaine de caractère, la dérivé était là! (non simplfiée certe)

Mais la simplfication est chose possible également. repérer dans l'arbre certain parcours de'*' est faisable.
(x^2 / x ) étant facilement repérable dans un arbre, permetait de renvoyer '1/x'.
La simplification marchait dans certains cas, j'ai pas été jusqu'au bout .

Enfin voila, tout dépend de ton but. Si c'est juste une calculette simple rien ne sert d'en arriver là, sinon c'est un exercice ou je m'étais éclaté

PS: volontier également de te proposer mon code, par MP si tu veux.