Présentation du problème

On souhaite évaluer une expression arithmétique (ou logique). Pour ce faire, il faut franchir plusieurs étapes qui font l'objet d'un exercice classique d'un cours de théorie des langages que nous n'aborderons ici que très superficiellement et de manière simplifiée.

Analyse lexicale

La première est l'analyse lexicale qui consiste à découper la suite des symboles qui constituent l'expression en unités lexicales ou jetons. Ces jetons doivent respecter des règles syn­ta­xi­ques, suite de chiffres pour un entier, suite de chiffres contenant éventuellement un point pour les nombres réels, symbole unique \(+,x,-,/\) pour les opérateurs arithmétiques, etc.

L'expression \(E\) ci-dessus fournit la liste de jetons suivante (la nature de chaque jeton est indiquée, valeur numérique, opérateur binaire, unaire, parenthèse) :

Analyse syntaxique

L'expression doit respecter une syntaxe, comme les formules de la logique propositionnelle par exemple. Il doit y avoir autant de parenthèses ouvrantes que fermantes, les opérations binaires doivent contenir deux opérandes de part et d'autre de l'opérateur, etc.

La description formelle de ces règles syntaxiques se fait à l'aide d'une grammaire décrivant un langage. Le rôle de l'analyse syntaxique est de retracer la suite des règles qui ont permis de construire l'expression en partant d'une règle appelée axiome. Cette analyse peut être ascendante ou descendante selon que l'on dérive les règles en partant de l'axiome pour aboutir à l'expression, ou que l'on déconstruit l'expression.*C'est cette approche que nous utilisons naïvement pour analyser l'expression.

Cette analyse permet de construire l'arbre syntaxique ou arbre de dérivation de l'expression. Chaque opération \(q\)-aire est codée par un arbre \(q\)-aire dont la racine est l'opérateur et les \(q\) fils sont les \(q\) opérandes.

Le procédé est éminemment récursif, si l'opérande est lui même une expression, il est remplacé par son arbre syntaxique jusqu'à obtenir une valeur atomique pour constituer une feuille de cet arbre.

Évaluation de l'expression

Cet arbre est ensuite traité par un algorithme récursif. Si sa racine contient une valeur (dans ce cas, le sous-arbre est une feuille), l'algorithme renvoie cette valeur . S'il s'agit d'un opérateur binaire, l'algorithme s'appelle récursivement sur les deux sous-arbres gauche et droit et une fois les deux valeurs de retour obtenues, il est en mesure d'effectuer l'opération et de renvoyer le résultat.

L'évaluation d'une expression arithmétique ou logique en notation infixe où les opérateurs binaires sont placés entre les opérandes est donc un problème qui n'a rien de trivial. On peut transformer une liste de jetons issus d'une expression infixe parenthésée en liste postfixe ou en arbre syntaxique à l'aide de l'algorithme de la voie de triage élaboré par E. Dijkstra (auteur de l'algorithme du plus court chemin qui porte son nom) et qui sera étudiée en 3ème année.

Expression postfixe et utilisation d'une pile

Notation postfixe

Une opération binaire, comme l'addition \(x+y\) dans \(\mathbb Z,\) ou la composition \(f\circ g\) de deux applications par exemple, peuvent s'exprimer d'autres manières, celle que nous venons d'employer, la notation infixe, étant la plus commune. On peut également utiliser la notation préfixe dans laquelle l'opérateur est placé avant les opérandes, notation généralement employée pour les fonctions, ici \(+\,(x,y),\) ou encore la notation postfixe \((x,y)\,+\) dans laquelle l'opérateur est placé après les opérandes. Dans le cas d'un opérateur unaire, les deux notations préfixe et postfixe coexistent souvent, comme \({\color{lightblue}-}3\) pour l'opposé de \(3\) ou \(M^{\color{olive}t}\) pour la transposée d'une matrice \(M,\) par exemple.

En notant sous forme postfixe \((a,b)\;\diamond\) l'expression infixe \(a\diamond b\) d'un opérateur binaire \(\diamond\) et \((a)\star\) celle d'un opérateur unaire \(\star a,\) l'expression \(E=\;\) fixée plus haut devient :

Les parenthèses ne sont représentées dans l'expression que pour mettre en évidence la logique du passage de la notation infixe à postfixe.

Évaluation à l'aide d'une pile

Plutôt que d'évaluer inductivement l'arbre de dérivation, on utilise une pile pour évaluer l'expression postfixe. L'algorithme est simple, on initialise une pile vide, puis on traite suc­ces­si­ve­ment chacun des termes/jetons de l'expression postfixe en lui appliquant l'une des trois règles exclusives suivantes :

1. Si c'est un opérande, alors on l'empile.
2. Si c'est un opérateur binaire \(\diamond,\) alors on dépile la valeur \(y\) au sommet de la pile puis la valeur \(x,\) puis on empile le résultat de l'opération \(x\diamond y\).
3. Si c'est un opérateur unaire \(\star,\) on dépile la valeur \(x\) au sommet de la pile, puis on empile le résultat de l'opération \(\star x\).

La table ci-dessous décrit l'état de la pile (sur fond clair) au fur et à mesure de la lecture des termes de l'expression postfixe précédente. La ligne inférieure contient les termes de l'expression à calculer et le contenu de la pile (après qu'une règle a été appliquée) est écrit au-dessus. Si l'expression syntaxiquement correcte, la pile ne doit con­te­nir que le résultat de l'évaluation (en orange) après le traitement du dernier jeton :

Certaines calculatrices utilisent toujours cette notation, comme la hp 15c entre autres (cf. photo d'un ex­emp­lai­re personnel de 1982 ci-dessous).

Calculatrice hp 15C, dite à notation polonaise inverse.

La pile était limitée à \(4\) niveaux* On peut démontrer que c'est suffisant pour évaluer n'importe quelle expression arithmétique ou logique. codés par \(4\) registres \(x,\) \(y,\) \(z\) et \(t,\) du sommet de la pile vers sa base, le registre \(x\) étant celui affiché à l'écran. On dispose d'une touche ENTER qui permet d'empiler un nombre une fois que l'on a fini de le saisir, alors que l'appui sur un opérateur lance le calcul immédiatement et agit sur les registres \(x\) et \(y\) s'il est binaire, sur le registre \(x\) s'il est unaire, cette calculatrice ne dispose donc pas d'une touche \(=.\) La touche \(x ⮂ y\) permet d'échanger les valeurs des deux registres \(x\) et \(y\) au sommet de la pile. Les touches  R⭣  et  R⭡  font respectivement descendre et monter les valeurs dans la pile.

Outre le mé­ca­nis­me d'évaluation beaucoup plus simple, cette notation présente un certain nombre d'avan­ta­ges décisifs :

1. Les parenthèses sont inutiles ;
2. Les résultats des calculs intermédiaires sont tous affichés ;
3. Les erreurs de calcul se décèlent plus facilement ;
4. Les résultats intermédiaires peuvent être réutilisés facilement.

Les inconvénients sont très limités. L'opérateur binaire de soustraction est distingué de l'opérateur unaire d'opposition (touche CHS^#CHange Sign sur la calculatrice), puisque l'opérateur doit suivre l'opérande, on écrit alors \(7.02\ \)CHS pour calculer l'opposé du nombre \(7.02\) (Vous remarquerez que si vous utilisez le symbole \(-\) dans une expression et qu'il agit comme un opérateur unaire, il est remplacé par le symbole \(\neg\) dans l'expression postfixe). D'autre part, la gymnastique d'esprit à acquérir pour transformer men­ta­le­ment une expression infixe en expression postfixe demande un certain temps d'ap­pren­tis­sage.

L'algorithme ÉvaluerPF s'en déduit directement et calque les règles 1 et 2 plus haut. Il utilise deux al­go­ri­thmes au­xi­liai­res, EstOp qui détermine si le caractère passé en paramètre représente ou non l'un des quatre opérateurs ari­thmé­ti­que, et Opérer qui réalise une opération binaire ou unaire.

ALGORITHME ÉvaluerPF(expr):valeur
donnees
   expr: liste de jetons
variables
   i: entier
   pile: liste
debut
   i ← 1
   pile ← ∅
   TQ (i ≤ #expr) FAIRE
      SI EstOpBin(expr[i]) ALORS
         y ← Dépiler(pile)
         x ← Dépiler(pile)
         z ← Opérer(x,y,expr[i])
         Empiler(pile,z)
      SINONSI EstOpUnr(expr[i]) ALORS
         x ← Dépiler(pile)
         z ← Opérer(x,expr[i])
         Empiler(pile,z)
      SINON
         Empiler(pile,expr[i])
      FSI
      i ← i + 1
   FTQ
   RENVOYER Depiler(pile)
FIN

Complexité

L'analyse est immédiate, si l'expression postfixe contient \(n\) termes, le nombre d'instructions à réaliser est en \(\Theta(n).\) En effet, selon la nature du terme courant, ces opérations sont : un empilement (opérande) ; deux dépilements, une opération arithmétique puis un empilement (opérateur). Dans les deux cas le coût est constant \(\Theta(1).\) On suppose ici que les opérations se font sur des nombres de taille bornée, sans quoi il faudrait bien sûr intégrer la complexité de l'opération effectuée fonction de la taille des deux opérandes. On a donc \(T(n)=\Theta(n).\)

Evaluer 2.25 3 ~ −

5.2500