notation infixée en notation postfixée
Le
ibiiztera
Bonjour.
Je cherche une méthode pour transformer une expression infixee en notatio=
n postfixee.
Comme par exemple:
((A+b)*c)**2
En
A b + c * 2 **
Vu qu'il s'agit d'un encodage utilisateur, ce serait plus simple de lire la=
notation infixee ensuite de faire les calculs en notation postfixee.
Merci.
Manuel DAHMEN.
Je cherche une méthode pour transformer une expression infixee en notatio=
n postfixee.
Comme par exemple:
((A+b)*c)**2
En
A b + c * 2 **
Vu qu'il s'agit d'un encodage utilisateur, ce serait plus simple de lire la=
notation infixee ensuite de faire les calculs en notation postfixee.
Merci.
Manuel DAHMEN.
parcours en profondeur, et on applique la récursion avant ou après
l'opération ... donc le mieux est de reconstruire un arbre et regénérer
l'autre ensuite
http://zanotti.univ-tln.fr/ALGORITHMIQUE/PARCOURS-FIXE.html
un ptit google avec les mots clés et t'as toutes les réponses....
Le 19/04/2012 14:16, ibiiztera a écrit :
Regarde le "Shunting Yard" de Dijkstra, par exemple à :
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
Sinon, le problème principal est de parser l'expression originale pour
construire un arbre, puis de faire un parcours postfixé de cet arbre ( il
n'est pas nécessaire de construire la liste postfixée). Pour tran sformer
le texte en arbre abstrait :
- soit tu utilises un générateur d'analyseur (par exemple JFlex +
JavaCup)
- soit tu écris toi-même l'analyseur, en utilisant par exemple une
descente récursive (sur wikipedia, Ã
http://en.wikipedia.org/wiki/Recursive_descent_parser l'exemple est
une simplification de ce que tu veux faire).
La complexité dépendra essentiellement de ton langage.
-- Alain.
je l'avais fait il y a longtemps avec un automate a pile. c'etait
rapide, et ca permettait aussi de calculer les dérivées formelles dont
j'avais besoins pour divers calculs (integration d'un systeme d'ED avec
calcul de la sensibilité des variable et optimisation)
NotMe
La méthode est facile. Il faut introduire un délimiteur et avoir un
dictionnaire des instructions autorisées et des fonctions
disponibles (avec leurs priorités relatives).
Exemple :
'(2+F(A+b)*c)**2'
'2+F(A+b)*c' 2 **
2 'F(A+b)*c' + 2 **
2 'F(A+b)' c * + 2 **
2 'A+b' F c * + 2 **
2 A b + F c * + 2 **
Si tu veux un code te donnant à peu près ce que tu veux, tu peux en
télécharger un ici : http://www.rpl2.fr et regarder le fichier
analyse_notation_algebrique.c.
La fonction prend une chaîne de caractère en notation algébrique et
la transforme en notation polonaise inversée (sous forme de chaîne
de caractères toujours) avant de l'analyser pour l'exécuter.
Ne reste plus qu'à convertir le code en Java ;-)
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr