Langage de programmation - Structure de données - Évaluation d'expression («Infix to Postfix»)

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 = 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.

PARTAGER CETTE PAGE SUR

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

	ABAP/4
	Ada
	Assembleur
	Assembly & bytecode
	ASP (Active Server Pages)
	Basic
	C
	C++
	C# (C Sharp)
	Cobol
	ColdFusion
	Fortran
	HTML
	Java
	JavaScript
	LISP
	Logo
	LotusScript
	Oberon
	Pascal
	Perl
	PHP
	PL/1
	Prolog
	Python
	Rebol
	REXX
	Ruby
	SAS
	NoSQL
	SQL
	Swift
	X++ (Axapta)

	Assembleur 370
	Assembleur 1802
	Assembleur 4004
	Assembleur 6502
	Assembleur 6800
	Assembleur 68000
	Assembleur 8080 et 8085
	Assembleur 8089
	Assembleur 80x86
	Assembleur AGC4
	Assembleur ARM
	Assembleur DPS 8000
	Assembleur i860
	Assembleur Itanium
	Assembleur MIPS
	Assembleur PDP-11
	Assembleur PowerPC
	Assembleur RISC-V
	Assembleur SPARC
	Assembleur SuperH
	Assembleur UNIVAC I
	Assembleur VAX
	Assembleur Z80
	Assembleur Z8000
	Assembleur z/Architecture

	CIL
	Jasmin
	LLVM
	MSIL
	Parrot
	P-Code (PCode)
	SWEET16

	ASP 1.0
	ASP 2.0
	ASP 3.0
	ASP.NET

	ABasiC (Amiga)
	Adam SmartBASIC
	Altair BASIC
	AmigaBASIC (Amiga)
	AMOS Basic (Amiga)
	Atari Basic (Atari 400, 600 XL, 800, 800XL)
	Basic Apple II (Integer BASIC/APPLESOFT)
	Basic Commodore 64 (CBM-BASIC)
	Basic Commodore 128 (BASIC 7.0)
	Basic Commodore VIC-20 (CBM-BASIC 2.0)
	Basic Coco 1 (Color Basic)
	Basic Coco 2 (Extended Color Basic)
	Basic Coco 3 (Extended Color Basic 2.0)
	BASICA (PC DOS)
	Basic Pro
	BBC BASIC
	Blitz BASIC (Amiga)
	DarkBASIC
	Dartmouth BASIC
	GFA-Basic (Atari ST/Amiga)
	GWBASIC (MS-DOS)
	Liberty BASIC
	Locomotive BASIC (Amstrad CPC)
	MSX-Basic
	Omikron Basic (Atari ST)
	Oric Extended Basic
	Power Basic
	Quick Basic/QBasic (MS-DOS)
	Sinclair BASIC (ZX80, ZX81, ZX Spectrum)
	ST BASIC (Atari ST)
	Turbo Basic
	Vintage BASIC
	VBScript
	Visual Basic (VB)
	Visual Basic .NET (VB .NET)
	Visual Basic pour DOS
	Yabasic

Section courante

A propos

Section administrative du site

Introduction

Le processus d'évaluation

Exemple

	C Shell Unix (csh)

	C pour Amiga
	C pour Atari ST
	C pour DOS
	C pour Falcon030
	C pour GEMDOS (Atari ST)
	C pour Linux
	C pour PowerTV OS
	C pour OS/2
	C pour Unix
	C pour Windows

	Aztec C
	CoCo-C
	GNU C
	HiSoft C
	IBM C/2
	Introl-C
	Lattice C
	Microsoft C
	MinGW C
	MSX-C
	Open Watcom C
	OS-9 C Compiler
	Pure C
	Quick C
	Turbo C

	C++ pour OS/2
	C++ pour Windows

	Borland C++
	C++Builder
	IBM VisualAge C++
	Intel C++
	MinGW C++
	Open Watcom C++
	Symantec C++
	Turbo C++
	Visual C++
	Visual C++ .NET
	Watcom C++
	Zortech C++

	Apple Pascal
	Delphi/Kylix/Lazarus
	Free Pascal
	GNU Pascal
	HighSpeed Pascal
	IBM Personal Computer Pascal
	Lisa Pascal
	Maxon Pascal
	MPW Pascal
	OS-9 Pascal
	OSS Personal Pascal
	Pascal-86
	Pascal du Cray Research
	Pascal/VS
	Pascal-XT
	PURE Pascal
	QuickPascal
	RemObjets Chrome
	Sun Pascal
	THINK Pascal
	Tiny Pascal (TRS-80)
	Turbo Pascal
	UCSD Pascal
	VAX Pascal
	Virtual Pascal

	Turbo Pascal for CP/M-80
	Turbo Pascal for DOS
	Turbo Pascal for Macintosh
	Turbo Pascal for Windows

	CodeIgniter (Cadre d'application)
	Drupal (Projet)
	Joomla! (Projet)
	Phalanger (PHP .NET)
	phpBB (Projet)
	Smarty (balise)
	Twig (balise)
	Symfony (Cadre d'application)
	WordPress (Projet)
	Zend (Cadre d'application)

	Btrieve
	Cassandra
	Clipper
	CouchDB
	dBASE
	Hbase
	Hypertable
	MongoDB
	Redis

	Access
	BigQuery
	DB2
	H2
	Interbase
	MySQL
	Oracle
	PostgreSQL
	SAP HANA
	SQL Server
	Sybase
	U-SQL

	Introduction
	Notion de typage
	Types scalaires
	Structure statique
	Types abstraits
	Structures dynamiques
	Structures dynamiques linéaires non-récursives (les fichiers)
	Structures récursives linéaires
	Structures récursives non linéaires
	Structures de données simples
	Structures adressables par leur contenu

	Évaluation d'expression («Infix to Postfix»)
	Évaluation d'expression (par remplacement)

	Recherche dichotomique (recherche binaire ou recherche logarithmique)
	Table haché (Hash Table)

	GNAT
	SMALLAda
	VHDL

	ASSEMBLER/MONITOR 64
	Micol Assembler

	A86
	MASM (Macro Assembler)
	TASM (Turbo Assembler)

	BeckerBASIC
	SIMONS' BASIC