Section courante

A propos

Section administrative du site

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 :

  1. Effectue une évaluation de gauche vers la droite.
  2. Si c'est un opérande, ajouter dans la pile.
  3. S'il s'agit d'un opérateur de l'opérande de la pile, il faut effectuer une opération.
  4. Entreposer la sortie dans l'étape 3, retour dans la pile.
  5. Balayer l'expression jusqu'à ce que tous les opérandes soient traités.
  6. 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 :

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace InfixToPostfixSamples
  7. {
  8.     class Program
  9.     {
  10.  
  11.         public static int Evaluate(string infix)
  12.         {
  13.             // Transformation en INFIX
  14.             Stack<char> stack = new Stack<char>();
  15.             StringBuilder postfix = new StringBuilder();
  16.  
  17.             if (infix[0] == '-') infix = '0' + infix;
  18.             for (int i = 0; i < infix.Length; i++)
  19.             {
  20.                 if ((infix[i] >= '0') && (infix[i] <= '9'))
  21.                 {
  22.                     postfix.Append(infix[i]);
  23.                 }
  24.                 else if (infix[i] == '(')
  25.                 {
  26.                     stack.Push(infix[i]);
  27.                 }
  28.                 else if ((infix[i] == '*') || (infix[i] == '+') || (infix[i] == '-') || (infix[i] == '/'))
  29.                 {
  30.                     while ((stack.Count > 0) && (stack.Peek() != '('))
  31.                     {
  32.                         char top = stack.Peek();
  33.                         char p_2 = infix[i];
  34.                         bool appendOk = true;
  35.  
  36.                         if (top == '+' && p_2 == '*') appendOk = false;
  37.                         else if (top == '*' && p_2 == '-') appendOk = true;
  38.                         else if (top == '+' && p_2 == '-') appendOk = true;
  39.  
  40.                         if (appendOk)
  41.                         {
  42.                             postfix.Append(stack.Pop());
  43.                         }
  44.                         else
  45.                         {
  46.                             break;
  47.                         }
  48.                     }
  49.                     stack.Push(infix[i]);
  50.                 }
  51.                 else if (infix[i] == ')')
  52.                 {
  53.                     while ((stack.Count > 0) && (stack.Peek() != '(')) postfix.Append(stack.Pop());
  54.                     if (stack.Count > 0) stack.Pop(); // Dépile à la gauche du '('
  55.                 }
  56.             }
  57.             while (stack.Count > 0) postfix.Append(stack.Pop());
  58.  
  59.             // Transformation en POSTFIX
  60.             Stack<int> resultStack = new Stack<int>();
  61.             for (int i = 0; i < postfix.Length; i++)
  62.             {
  63.                 if ((postfix[i] == '*') || (postfix[i] == '+') || (postfix[i] == '-') || (postfix[i] == ' '))
  64.                 {
  65.                     int result;
  66.                     int p = resultStack.Pop();
  67.                     int p2 = resultStack.Pop();
  68.                     switch (postfix[i])
  69.                     {
  70.                         case '+': result = p2 + p; break;
  71.                         case '-': result = p2 - p; break;
  72.                         case '*': result = p2 * p; break;
  73.                         case '/': result = p2 / p; break;
  74.                         default: result = -1; break;
  75.                     }
  76.                     resultStack.Push(result);
  77.                 }
  78.                 else if ((postfix[i] >= '0') || (postfix[i] <= '9'))
  79.                 {
  80.                     resultStack.Push((int)(postfix[i] - '0'));
  81.                 }
  82.             }
  83.             return resultStack.Pop();
  84.         }
  85.  
  86.         static void Main(string[] args)
  87.         {
  88.             Console.Write("8 * 8 + 2 = ");
  89.             Console.WriteLine(Evaluate("8 * 8 + 2"));
  90.             Console.Write("(4 + 7) * 3 = ");
  91.             Console.WriteLine(Evaluate("(4 + 7) * 3"));
  92.             Console.Write("(4 - 7) * 3 = ");
  93.             Console.WriteLine(Evaluate("(4 - 7) * 3"));
  94.             Console.Write("-(4 - 7) * 3 = ");
  95.             Console.WriteLine(Evaluate("-(4 - 7) * 3"));
  96.         }
  97.     }
  98. }

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 :

  1. Program EvalSamples;
  2.  
  3. Var
  4.  Stack:Array[0..100]of Char;
  5.  TopOfStack:Byte;
  6.  resultStack:Array[0..100]of LongInt;
  7.  TopOfStackInt:Byte;
  8.  
  9. Procedure StackPush(C:Char);Begin
  10.  If TopOfStack>=High(Stack)Then Begin
  11.   WriteLn('Pile pleine!');
  12.   Halt;
  13.  End
  14.   Else
  15.  Begin
  16.   Stack[TopOfStack]:=C;
  17.   Inc(TopOfStack);
  18.  End;
  19. End;
  20.  
  21. Function StackPop:Char;Begin
  22.  Dec(TopOfStack);
  23.  If TopOfStack<1Then Begin
  24.   WriteLn('Pile vide');
  25.   Halt;
  26.  End
  27.   Else
  28.  StackPop:=Stack[TopOfStack];
  29. End;
  30.  
  31. Function StackPeek:Char;Begin
  32.  StackPeek:=Stack[TopOfStack-1];
  33. End;
  34.  
  35. Procedure ResultStackPush(C:LongInt);Begin
  36.  If TopOfStackInt>=High(ResultStack)Then Begin
  37.   WriteLn('Pile pleine!');
  38.   Halt;
  39.  End
  40.   Else
  41.  Begin
  42.   ResultStack[TopOfStackInt]:=C;
  43.   Inc(TopOfStackInt);
  44.  End;
  45. End;
  46.  
  47. Function ResultStackPop:LongInt;Begin
  48.  Dec(TopOfStackInt);
  49.  If TopOfStackInt<1Then Begin
  50.   WriteLn('Pile vide');
  51.   Halt;
  52.  End
  53.   Else
  54.  ResultStackPop:=ResultStack[TopOfStackInt];
  55. End;
  56.  
  57. Function Evaluate(Infix:String):Integer;
  58. Var
  59.  I:Byte;
  60.  Top,P_2:Char;
  61.  AppendOk:Boolean;
  62.  _Result,P,P2:LongInt;
  63.  Err:Word;
  64.  PostFix:String;
  65.  Value:String;
  66. Begin
  67.  TopOfStack:=1;
  68.  TopOfStackInt:=1;
  69.  PostFix:='';
  70.  If Infix[1]='-'Then Infix:='0'+Infix;
  71.  For I:=1 to Length(Infix)do Begin
  72.   If Infix[I]in['0'..'9']Then PostFix:=PostFix+Infix[I]
  73.   Else If Infix[I]='('Then StackPush(Infix[I])
  74.   Else If Infix[I]in['*','+','-','/']Then Begin
  75.    While(TopOfStack>1)and(StackPeek <> '(')do Begin
  76.     Top:=StackPeek;
  77.     P_2:=Infix[I];
  78.     AppendOk:=True;
  79.     If(Top='+')and(P_2='*')Then AppendOk:=False
  80.     Else If(Top='*')and(P_2='-')Then AppendOk:=True
  81.     Else If(Top='+')and(P_2='-')Then AppendOk:=True;
  82.     If(AppendOk)Then PostFix:=PostFix+StackPop
  83.                 Else Break;
  84.    End;
  85.    StackPush(Infix[I]);
  86.   End
  87.   Else If Infix[I]=')'Then Begin
  88.    While(TopOfStack>1)and(StackPeek<>'(')do PostFix:=PostFix+StackPop;
  89.    If TopOfStack>1Then StackPop;
  90.   End;
  91.  End;
  92.  While(TopOfStack>1)do PostFix:=PostFix+StackPop;
  93.   { Transformation en POSTFIX }
  94.  For I:=1 to Length(PostFix) do Begin
  95.   If PostFix[I]in['*','+','-',' ']Then Begin
  96.    P:=ResultStackPop;
  97.    P2:=ResultStackPop;
  98.    Case PostFix[I]of
  99.     '+':_Result:=P2+P;
  100.     '-':_Result:=P2-P;
  101.     '*':_Result:=P2*P;
  102.     '/':_Result:=P2 mod P;
  103.     Else _Result:=-1;
  104.    End;
  105.    ResultStackPush(_Result);
  106.   End
  107.    Else
  108.   If PostFix[I] in['0'..'9']Then ResultStackPush(Byte(PostFix[I])-Byte('0'));
  109.  End;
  110.  Evaluate:=ResultStackPop;
  111. End;
  112.  
  113. BEGIN
  114.  WriteLn('8 * 8 + 2 = ',Evaluate('8 * 8 + 2'));
  115.  WriteLn('(4 + 7) * 3 = ',Evaluate('(4 + 7) * 3'));
  116.  WriteLn('(4 - 7) * 3 = ',Evaluate('(4 - 7) * 3'));
  117.  WriteLn('-(4 - 7) * 3 = ',Evaluate('-(4 - 7) * 3'));
  118. END.

Voici un programme plus évoluer en Free Pascal :

  1. Program EvalSamples;
  2.  
  3. Var
  4.  Stack:Array[0..100]of Char;
  5.  TopOfStack:Byte;
  6.  resultStack:Array[0..100]of LongInt;
  7.  TopOfStackInt:Byte;
  8.  
  9. Procedure StackPushChar(C:Char);Begin
  10.  If TopOfStack>=High(Stack)Then Begin
  11.   WriteLn('Pile pleine!');
  12.   Halt;
  13.  End
  14.   Else
  15.  Begin
  16.   Stack[TopOfStack]:=C;
  17.   Inc(TopOfStack);
  18.  End;
  19. End;
  20.  
  21. Function StackPop:String;
  22. Var
  23.  S:String;
  24.  Err:Word;
  25. Begin
  26.  Dec(TopOfStack);
  27.  If TopOfStack<1Then Begin
  28.   WriteLn('Pile vide');
  29.   Halt;
  30.  End
  31.   Else
  32.  StackPop:=Stack[TopOfStack];
  33. End;
  34.  
  35. Function StackPeek:Char;Begin
  36.  StackPeek:=Stack[TopOfStack-1];
  37. End;
  38.  
  39. Procedure ResultStackPush(C:LongInt);Begin
  40.  If TopOfStackInt>=High(ResultStack)Then Begin
  41.   WriteLn('Pile pleine!');
  42.   Halt;
  43.  End
  44.   Else
  45.  Begin
  46.   ResultStack[TopOfStackInt]:=C;
  47.   Inc(TopOfStackInt);
  48.  End;
  49. End;
  50.  
  51. Function ResultStackPop:LongInt;Begin
  52.  Dec(TopOfStackInt);
  53.  If TopOfStackInt<1Then Begin
  54.   WriteLn('Pile vide');
  55.   Halt;
  56.  End
  57.   Else
  58.  ResultStackPop:=ResultStack[TopOfStackInt];
  59. End;
  60.  
  61. Function Evaluate(Infix:String):Integer;
  62. Var
  63.  I:Byte;
  64.  Top,P_2:Char;
  65.  AppendOk:Boolean;
  66.  _Result,P,P2:LongInt;
  67.  Err:Word;
  68.  PostFix:String;
  69.  Value:String;
  70. Begin
  71.  TopOfStack:=1;
  72.  TopOfStackInt:=1;
  73.  PostFix:='';
  74.  If Infix[1]='-'Then Infix:='(0)'+Infix;
  75.  I:=1;
  76.  Repeat
  77.   If Infix[I]in['0'..'9']Then Begin
  78.    Value:='';
  79.    Repeat
  80.     If Infix[I]in['0'..'9']Then Begin
  81.      Value:=Value+Infix[I];
  82.      Inc(I);
  83.     End
  84.      Else
  85.     Break;
  86.    Until I>Length(Infix);
  87.    PostFix:=PostFix+'('+Value+')';
  88.   End
  89.   Else If Infix[I]='('Then Begin
  90.    StackPushChar(Infix[I]);
  91.    Inc(I);
  92.   End
  93.   Else If Infix[I]in['*','+','-','/']Then Begin
  94.    While(TopOfStack>1)and(StackPeek <> '(')do Begin
  95.     Top:=StackPeek;
  96.     P_2:=Infix[I];
  97.     AppendOk:=True;
  98.     If(Top='+')and(P_2='*')Then AppendOk:=False
  99.     Else If(Top='*')and(P_2='-')Then AppendOk:=True
  100.     Else If(Top='+')and(P_2='-')Then AppendOk:=True;
  101.     If(AppendOk)Then PostFix:=PostFix+StackPop
  102.                 Else Break;
  103.    End;
  104.    StackPushChar(Infix[I]);
  105.    Inc(I);
  106.   End
  107.   Else If Infix[I]=')'Then Begin
  108.    While(TopOfStack>1)and(StackPeek<>'(')do PostFix:=PostFix+StackPop;
  109.    If TopOfStack>1Then StackPop;
  110.    Inc(I);
  111.   End
  112.    Else
  113.   Inc(I);
  114.  Until I>Length(Infix);
  115.  While(TopOfStack>1)do PostFix:=PostFix+StackPop;
  116.   { Transformation en POSTFIX }
  117.  I:=1;
  118.  Repeat
  119.   If PostFix[I]in['*','+','-',' ']Then Begin
  120.    P:=ResultStackPop;
  121.    P2:=ResultStackPop;
  122.    Case PostFix[I]of
  123.     '+':_Result:=P2+P;
  124.     '-':_Result:=P2-P;
  125.     '*':_Result:=P2*P;
  126.     '/':_Result:=P2 mod P;
  127.     Else _Result:=-1;
  128.    End;
  129.    ResultStackPush(_Result);
  130.   End
  131.    Else
  132.   Begin
  133.    Value:='';
  134.    Repeat
  135.     If Postfix[I]in['0'..'9']Then Begin
  136.      Value:=Value+Postfix[I];
  137.      Inc(I);
  138.     End
  139.      Else
  140.     Break;
  141.    Until I>Length(Postfix);
  142.    If Value<>''Then Begin
  143.     Val(Value,_Result,Err);
  144.     ResultStackPush(_Result);
  145.    End;
  146.   End;
  147.   Inc(I);
  148.  Until I>Length(Postfix);
  149.  Evaluate:=ResultStackPop;
  150. End;
  151.  
  152. BEGIN
  153.  WriteLn('8*8+2 = ',Evaluate('8*8+2'));
  154.  WriteLn('8 * 8 + 2 = ',Evaluate('8 * 8 + 2'));
  155.  WriteLn('(4 + 7) * 3 = ',Evaluate('(4 + 7) * 3'));
  156.  WriteLn('(4 - 7) * 3 = ',Evaluate('(4 - 7) * 3'));
  157.  WriteLn('-(4 - 7) * 3 = ',Evaluate('-(4 - 7) * 3'));
  158.  WriteLn('12 * 12 = ',Evaluate('12 * 12'));
  159.  WriteLn('-12*12 = ',Evaluate('-12 * 12'));
  160. END.

on obtiendra le résultat suivant :

8*8+2 = 66
8 * 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.



Dernière mise à jour : Mercredi, le 19 avril 2017