Algorithme conversion postfixée vers infixée

[Onimaru]

Salut, je cherche l’algorithme qui permet de convertir une expression arithmétique postfixée vers une expression infixée.

[Franck Dernoncourt]

As-tu cherché sur Google quelque chose du genre "convert postfix to infix" ? Il semble y avoir beaucoup de résultats.

[Onimaru]

Envoyé par Franck Dernoncourt

As-tu cherché sur Google quelque chose du genre "convert postfix to infix" ? Il semble y avoir beaucoup de résultats.

Salut, en effet j'ai cherché sur Google, mais il donne toujours "infix to postfix".
En tout cas moi je cherche les étapes à suivre pour faire la conversion en utilisant une pile.

[Franck Dernoncourt]

http://www.cs.man.ac.uk/~pjj/cs212/fix.html :

Converting between these notations

The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:
Infix	                    Postfix	         Prefix
( (A * B) + (C / D) )	( (A B *) (C D /) +)	(+ (* A B) (/ C D) )
((A * (B + C) ) / D)	( (A (B C +) *) D /)	(/ (* A (+ B C) ) D)
(A * (B + (C / D) ) )	(A (B (C D /) +) *)	(* A (+ B (/ C D) ) )
You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.
You can use a similar trick to convert to and from parse trees - each bracketed triplet of an operator and its two operands (or sub-expressions) corresponds to a node of the tree. The corresponding parse trees are:

			      /			   *
      +			     / \		  / \
     / \		    *   D		 A   +
    /   \		   / \			    / \
   *     /		  A   +			   B   /
  / \   / \		     / \		      / \
 A   B C   D		    B   C		     C   D

((A*B)+(C/D))		((A*(B+C))/D) 		(A*(B+(C/D)))

[Onimaru]

Envoyé par Franck Dernoncourt

http://www.cs.man.ac.uk/~pjj/cs212/fix.html :

Converting between these notations

The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:
Infix	                    Postfix	         Prefix
( (A * B) + (C / D) )	( (A B *) (C D /) +)	(+ (* A B) (/ C D) )
((A * (B + C) ) / D)	( (A (B C +) *) D /)	(/ (* A (+ B C) ) D)
(A * (B + (C / D) ) )	(A (B (C D /) +) *)	(* A (+ B (/ C D) ) )
You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.
You can use a similar trick to convert to and from parse trees - each bracketed triplet of an operator and its two operands (or sub-expressions) corresponds to a node of the tree. The corresponding parse trees are:

			      /			   *
      +			     / \		  / \
     / \		    *   D		 A   +
    /   \		   / \			    / \
   *     /		  A   +			   B   /
  / \   / \		     / \		      / \
 A   B C   D		    B   C		     C   D

((A*B)+(C/D))		((A*(B+C))/D) 		(A*(B+(C/D)))

Merci pour l'aide.
D’après ce que je comprends ce procédé est récursif. Je cherche la version itérative qui utilise une pile, le processus inverse de "infix->postfix".

[Franck Dernoncourt]

http://wiki.answers.com/Q/How_do_you..._infix_in_Java ?

[Onimaru]

Envoyé par Franck Dernoncourt

http://wiki.answers.com/Q/How_do_you..._infix_in_Java ?

Oui c'est ça , mais je veux l'algorithme claire, les instructions quoi, l'implémentation dans n'importe quel langage c'est une autre affaire.
Un truc du genre :
(infixée->postfixée)
On traite séquentiellement l'expression infixée (EI). Selon le symbole en cours :
1) Opérande -> l'ajouter à l'expression postfixée (EP).
2) '(' -> l'empiler dans la pile des symboles (PS).
3) ')' -> répéter dépiler l'opérateur depuis PS puis l''ajouter à EP jusqu'à trouver le '(', puis dépiler PS pour se débarrasser du '('.
4) Opérateur -> Si la pile est vide alors empiler l'opérateur sinon
tant que l'opérateur au sommet de la pile est moins prioritaire ou égal à la priorité de l'opérateur en cours dépiler et ajouter à EP. enfin empiler l'opérateur.

Moi je veux le processus inverse.

[souviron34]

oui, eh bien ça doit bien être ça le sujet de ton boulot, non ?

Alors cherche et propose

[Onimaru]

Envoyé par souviron34

oui, eh bien ça doit bien être ça le sujet de ton boulot, non ?

Alors cherche et propose

tu me prends pour qui ???
Regarde mes discussions avant de dire n'importe quoi.