notation infixée en notation postfixée

4 réponses
Avatar
ibiiztera
Bonjour.
Je cherche une m=E9thode 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.

4 réponses

Avatar
pif34
pour générer une écriture pré ou post fixée, on créé passe par un arbre,
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 :
Bonjour.
Je cherche une méthode pour transformer une expression infixee en notation 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.
Avatar
Alain Ketterlin
ibiiztera writes:

Je cherche une méthode pour transformer une expression infixee en
notation 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.



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.
Avatar
NotMe
Le 19/04/2012 14:16, ibiiztera a écrit :
Bonjour.
Je cherche une méthode pour transformer une expression infixee en notation 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 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)
Avatar
JKB
Le Fri, 20 Apr 2012 13:01:44 +0200,
NotMe écrivait :
Le 19/04/2012 14:16, ibiiztera a écrit :
Bonjour.
Je cherche une méthode pour transformer une expression infixee en notation 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 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)



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