Introduction
L'algorithme de «Infix to Postfix», est l'un des algorithmes les plus célèbres pour effectuer l'évaluation d'une expression mathématique dans une chaine de caractères. On utilise beaucoup cette algorithme dans de nombreuses subtilité de programme, comme par exemple, dans l'évaluation d'une cellule d'un tableur (chiffrier électronique), dans certains interpréteur de commande Linux, dans des calculatrices programmables et même dans certains langages de programmation comme Perl (eval), PHP (eval), Python (eval), Snobol (EVAL), Liberty BASIC (Eval, Eval$) ASP 3.0 classique (Eval) par exemple.
La paternité de cette algorithme est difficile a déterminer, puisque l'algorithme a évolué au fil du XXiècle. Ainsi, les premières idées appelé à ce moment là, RPN, pour l'abréviation de l'anglicisme Reverse Polish notation, provienne du polonais Jan Lukasiewicz dans les années 1920. Ensuite, il a été exposé, en 1954, par Burks, Warren et Wright dans la publication «An Analysis of a Logical Machine Using Parenthesis-Free Notation». Finalement, il a été amélioré par Friedrich L. Bauer et Edsger W. Dijkstra afin qu'il utilise la pile de données.
Le processus d'évaluation
L'idée dernier cette algorithme c'est qu'il faut passer par 3 niveaux de manipulation de l'expression, afin que l'expression soit dans un ordre allant pouvoir être traiter facilement et surtout, on n'aura pas à se soucier des parenthèses, car l'expression aura déjà l'ordre voulu ! Voici quelques exemples des différences entre les 3 niveaux :
Expression Infix | Expression Prefix | Expression Postfix |
---|---|---|
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 * + |
A + B + C + D | + + + A B C D | A B + C + D + |
1 + 2 + 3 + 4 | + + + 1 2 3 4 | 1 2 + 3 + 4 + |
Lorsque l'on arrive au niveau Postfix, il devient très facile de traiter l'opération. On prend les deux premiers nombres et on applique l'opérande, on fait se genre de passage jusqu'à ce qu'il ne soit plus possible de simplifier l'opération. Prenons par exemple :
Passage | Expression |
---|---|
1 | 1 2 + 3 + 4 + |
2 | 3 3 + 4 + |
3 | 6 4 + |
4 | 10 |
Le processus d'évaluation s'effectuer selon les 6 étapes suivantes :
- Effectue une évaluation de gauche vers la droite.
- Si c'est un opérande, ajouter dans la pile.
- S'il s'agit d'un opérateur de l'opérande de la pile, il faut effectuer une opération.
- Entreposer la sortie dans l'étape 3, retour dans la pile.
- Balayer l'expression jusqu'à ce que tous les opérandes soient traités.
- Dépiler la pile et traiter l'opération.
Exemple
L'exemple suivant, écrit en langage de programmation C#, est très simplifié, et permet uniquement le traitement de nombre entier avec des opérateurs «+», «-», «*» et «/», ainsi que les parenthèses :
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
-
- namespace InfixToPostfixSamples
- {
- class Program
- {
-
- public static int Evaluate(string infix)
- {
- // Transformation en INFIX
- Stack<char> stack = new Stack<char>();
- StringBuilder postfix = new StringBuilder();
-
- if (infix[0] == '-') infix = '0' + infix;
- for (int i = 0; i < infix.Length; i++)
- {
- if ((infix[i] >= '0') && (infix[i] <= '9'))
- {
- postfix.Append(infix[i]);
- }
- else if (infix[i] == '(')
- {
- stack.Push(infix[i]);
- }
- else if ((infix[i] == '*') || (infix[i] == '+') || (infix[i] == '-') || (infix[i] == '/'))
- {
- while ((stack.Count > 0) && (stack.Peek() != '('))
- {
- char top = stack.Peek();
- char p_2 = infix[i];
- bool appendOk = true;
-
- if (top == '+' && p_2 == '*') appendOk = false;
- else if (top == '*' && p_2 == '-') appendOk = true;
- else if (top == '+' && p_2 == '-') appendOk = true;
-
- if (appendOk)
- {
- postfix.Append(stack.Pop());
- }
- else
- {
- break;
- }
- }
- stack.Push(infix[i]);
- }
- else if (infix[i] == ')')
- {
- while ((stack.Count > 0) && (stack.Peek() != '(')) postfix.Append(stack.Pop());
- if (stack.Count > 0) stack.Pop(); // Dépile à la gauche du '('
- }
- }
- while (stack.Count > 0) postfix.Append(stack.Pop());
-
- // Transformation en POSTFIX
- Stack<int> resultStack = new Stack<int>();
- for (int i = 0; i < postfix.Length; i++)
- {
- if ((postfix[i] == '*') || (postfix[i] == '+') || (postfix[i] == '-') || (postfix[i] == ' '))
- {
- int result;
- int p = resultStack.Pop();
- int p2 = resultStack.Pop();
- switch (postfix[i])
- {
- case '+': result = p2 + p; break;
- case '-': result = p2 - p; break;
- case '*': result = p2 * p; break;
- case '/': result = p2 / p; break;
- default: result = -1; break;
- }
- resultStack.Push(result);
- }
- else if ((postfix[i] >= '0') || (postfix[i] <= '9'))
- {
- resultStack.Push((int)(postfix[i] - '0'));
- }
- }
- return resultStack.Pop();
- }
-
- static void Main(string[] args)
- {
- Console.Write("8 * 8 + 2 = ");
- Console.WriteLine(Evaluate("8 * 8 + 2"));
- Console.Write("(4 + 7) * 3 = ");
- Console.WriteLine(Evaluate("(4 + 7) * 3"));
- Console.Write("(4 - 7) * 3 = ");
- Console.WriteLine(Evaluate("(4 - 7) * 3"));
- Console.Write("-(4 - 7) * 3 = ");
- Console.WriteLine(Evaluate("-(4 - 7) * 3"));
- }
- }
- }
on obtiendra le résultat suivant :
8 * 8 + 2 = 66(4 + 7) * 3 = 33
(4 - 7) * 3 = -9
-(4 - 7) * 3 = 9
Voici un programme équivalent écrit en Turbo Pascal :
- Program EvalSamples;
-
- Var
- Stack:Array[0..100]of Char;
- TopOfStack:Byte;
- resultStack:Array[0..100]of LongInt;
- TopOfStackInt:Byte;
-
- Procedure StackPush(C:Char);Begin
- If TopOfStack>=High(Stack)Then Begin
- WriteLn('Pile pleine!');
- Halt;
- End
- Else
- Begin
- Stack[TopOfStack]:=C;
- Inc(TopOfStack);
- End;
- End;
-
- Function StackPop:Char;Begin
- Dec(TopOfStack);
- If TopOfStack<1Then Begin
- WriteLn('Pile vide');
- Halt;
- End
- Else
- StackPop:=Stack[TopOfStack];
- End;
-
- Function StackPeek:Char;Begin
- StackPeek:=Stack[TopOfStack-1];
- End;
-
- Procedure ResultStackPush(C:LongInt);Begin
- If TopOfStackInt>=High(ResultStack)Then Begin
- WriteLn('Pile pleine!');
- Halt;
- End
- Else
- Begin
- ResultStack[TopOfStackInt]:=C;
- Inc(TopOfStackInt);
- End;
- End;
-
- Function ResultStackPop:LongInt;Begin
- Dec(TopOfStackInt);
- If TopOfStackInt<1Then Begin
- WriteLn('Pile vide');
- Halt;
- End
- Else
- ResultStackPop:=ResultStack[TopOfStackInt];
- End;
-
- Function Evaluate(Infix:String):Integer;
- Var
- I:Byte;
- Top,P_2:Char;
- AppendOk:Boolean;
- _Result,P,P2:LongInt;
- Err:Word;
- PostFix:String;
- Value:String;
- Begin
- TopOfStack:=1;
- TopOfStackInt:=1;
- PostFix:='';
- If Infix[1]='-'Then Infix:='0'+Infix;
- For I:=1 to Length(Infix)do Begin
- If Infix[I]in['0'..'9']Then PostFix:=PostFix+Infix[I]
- Else If Infix[I]='('Then StackPush(Infix[I])
- Else If Infix[I]in['*','+','-','/']Then Begin
- While(TopOfStack>1)and(StackPeek <> '(')do Begin
- Top:=StackPeek;
- P_2:=Infix[I];
- AppendOk:=True;
- If(Top='+')and(P_2='*')Then AppendOk:=False
- Else If(Top='*')and(P_2='-')Then AppendOk:=True
- Else If(Top='+')and(P_2='-')Then AppendOk:=True;
- If(AppendOk)Then PostFix:=PostFix+StackPop
- Else Break;
- End;
- StackPush(Infix[I]);
- End
- Else If Infix[I]=')'Then Begin
- While(TopOfStack>1)and(StackPeek<>'(')do PostFix:=PostFix+StackPop;
- If TopOfStack>1Then StackPop;
- End;
- End;
- While(TopOfStack>1)do PostFix:=PostFix+StackPop;
- { Transformation en POSTFIX }
- For I:=1 to Length(PostFix) do Begin
- If PostFix[I]in['*','+','-',' ']Then Begin
- P:=ResultStackPop;
- P2:=ResultStackPop;
- Case PostFix[I]of
- '+':_Result:=P2+P;
- '-':_Result:=P2-P;
- '*':_Result:=P2*P;
- '/':_Result:=P2 mod P;
- Else _Result:=-1;
- End;
- ResultStackPush(_Result);
- End
- Else
- If PostFix[I] in['0'..'9']Then ResultStackPush(Byte(PostFix[I])-Byte('0'));
- End;
- Evaluate:=ResultStackPop;
- End;
-
- BEGIN
- WriteLn('8 * 8 + 2 = ',Evaluate('8 * 8 + 2'));
- WriteLn('(4 + 7) * 3 = ',Evaluate('(4 + 7) * 3'));
- WriteLn('(4 - 7) * 3 = ',Evaluate('(4 - 7) * 3'));
- WriteLn('-(4 - 7) * 3 = ',Evaluate('-(4 - 7) * 3'));
- END.
Voici un programme plus évoluer en Free Pascal :
- Program EvalSamples;
-
- Var
- Stack:Array[0..100]of Char;
- TopOfStack:Byte;
- resultStack:Array[0..100]of LongInt;
- TopOfStackInt:Byte;
-
- Procedure StackPushChar(C:Char);Begin
- If TopOfStack>=High(Stack)Then Begin
- WriteLn('Pile pleine!');
- Halt;
- End
- Else
- Begin
- Stack[TopOfStack]:=C;
- Inc(TopOfStack);
- End;
- End;
-
- Function StackPop:String;
- Var
- S:String;
- Err:Word;
- Begin
- Dec(TopOfStack);
- If TopOfStack<1Then Begin
- WriteLn('Pile vide');
- Halt;
- End
- Else
- StackPop:=Stack[TopOfStack];
- End;
-
- Function StackPeek:Char;Begin
- StackPeek:=Stack[TopOfStack-1];
- End;
-
- Procedure ResultStackPush(C:LongInt);Begin
- If TopOfStackInt>=High(ResultStack)Then Begin
- WriteLn('Pile pleine!');
- Halt;
- End
- Else
- Begin
- ResultStack[TopOfStackInt]:=C;
- Inc(TopOfStackInt);
- End;
- End;
-
- Function ResultStackPop:LongInt;Begin
- Dec(TopOfStackInt);
- If TopOfStackInt<1Then Begin
- WriteLn('Pile vide');
- Halt;
- End
- Else
- ResultStackPop:=ResultStack[TopOfStackInt];
- End;
-
- Function Evaluate(Infix:String):Integer;
- Var
- I:Byte;
- Top,P_2:Char;
- AppendOk:Boolean;
- _Result,P,P2:LongInt;
- Err:Word;
- PostFix:String;
- Value:String;
- Begin
- TopOfStack:=1;
- TopOfStackInt:=1;
- PostFix:='';
- If Infix[1]='-'Then Infix:='(0)'+Infix;
- I:=1;
- Repeat
- If Infix[I]in['0'..'9']Then Begin
- Value:='';
- Repeat
- If Infix[I]in['0'..'9']Then Begin
- Value:=Value+Infix[I];
- Inc(I);
- End
- Else
- Break;
- Until I>Length(Infix);
- PostFix:=PostFix+'('+Value+')';
- End
- Else If Infix[I]='('Then Begin
- StackPushChar(Infix[I]);
- Inc(I);
- End
- Else If Infix[I]in['*','+','-','/']Then Begin
- While(TopOfStack>1)and(StackPeek <> '(')do Begin
- Top:=StackPeek;
- P_2:=Infix[I];
- AppendOk:=True;
- If(Top='+')and(P_2='*')Then AppendOk:=False
- Else If(Top='*')and(P_2='-')Then AppendOk:=True
- Else If(Top='+')and(P_2='-')Then AppendOk:=True;
- If(AppendOk)Then PostFix:=PostFix+StackPop
- Else Break;
- End;
- StackPushChar(Infix[I]);
- Inc(I);
- End
- Else If Infix[I]=')'Then Begin
- While(TopOfStack>1)and(StackPeek<>'(')do PostFix:=PostFix+StackPop;
- If TopOfStack>1Then StackPop;
- Inc(I);
- End
- Else
- Inc(I);
- Until I>Length(Infix);
- While(TopOfStack>1)do PostFix:=PostFix+StackPop;
- { Transformation en POSTFIX }
- I:=1;
- Repeat
- If PostFix[I]in['*','+','-',' ']Then Begin
- P:=ResultStackPop;
- P2:=ResultStackPop;
- Case PostFix[I]of
- '+':_Result:=P2+P;
- '-':_Result:=P2-P;
- '*':_Result:=P2*P;
- '/':_Result:=P2 mod P;
- Else _Result:=-1;
- End;
- ResultStackPush(_Result);
- End
- Else
- Begin
- Value:='';
- Repeat
- If Postfix[I]in['0'..'9']Then Begin
- Value:=Value+Postfix[I];
- Inc(I);
- End
- Else
- Break;
- Until I>Length(Postfix);
- If Value<>''Then Begin
- Val(Value,_Result,Err);
- ResultStackPush(_Result);
- End;
- End;
- Inc(I);
- Until I>Length(Postfix);
- Evaluate:=ResultStackPop;
- End;
-
- BEGIN
- WriteLn('8*8+2 = ',Evaluate('8*8+2'));
- WriteLn('8 * 8 + 2 = ',Evaluate('8 * 8 + 2'));
- WriteLn('(4 + 7) * 3 = ',Evaluate('(4 + 7) * 3'));
- WriteLn('(4 - 7) * 3 = ',Evaluate('(4 - 7) * 3'));
- WriteLn('-(4 - 7) * 3 = ',Evaluate('-(4 - 7) * 3'));
- WriteLn('12 * 12 = ',Evaluate('12 * 12'));
- WriteLn('-12*12 = ',Evaluate('-12 * 12'));
- END.
on obtiendra le résultat suivant :
8*8+2 = 668 * 8 + 2 = 66
(4 + 7) * 3 = 33
(4 - 7) * 3 = -9
-(4 - 7) * 3 = 9
12 * 12 = 144
-12*12 = -144
En se basant sur petit programme, on pourra l'étendre avec le support des exposants, de nombre réel et même l'application de formule.