Évaluation d'une expression avec une pile

Présentation du problème

On souhaite évaluer une expression arithmétique (ou logique), par exemple l'expression

\(E:=\) .

Pour en calculer la valeur, 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. 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 \(+,*,-,/\) 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 gauche, parenthèse droite) :

Segmentation de l'expression \(E\) en jetons.

Une expression arithmétique correcte doit respecter une certaine syntaxe. Il doit y avoir autant de parenthèses ouvrantes que de parenthèses 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 se fait à l'aide d'une grammaire décrivant le langage des expressions possibles. 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 part de l'axiome pour dériver les règles et aboutir à l'expression ou que l'on part de l'expression en reconstruisant à l'envers cette suite (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. Par exemple, l'opération \(8-3\) est codée par l'arbre binaire ci-dessous :

Arbre binaire représentant l'opération \(8-3\).

Si l'opérande est lui même une expression, comme dans \(1.2\times(8-3)\) où \(8-3\) est l'opérande droit de l'opérateur binaire \(\times\), la feuille de l'arbre binaire associé est remplacée par le sous-arbre représentant l'expression \(8-3\). L'expression \[1.2\times(8-3)\times 3 + ((3-1)\times 2)\times 3\] a pour arbre de dérivation :

Arbre de dérivation de l'expression arithmétique \(E=1.2\times(8-3)\times 3 + ((3-1)\times 2)\times 3.\) .

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.

NB. 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 gare de triage élaboré par E. Dijkstra (auteur de l'algorithme du plus court chemin qui porte son nom).

Expression postfixe et utilisation d'une pile

On rappelle qu'une opération binaire, comme l'addition dans \(\mathbb Z\) par exemple peut se noter de plu­sieurs façons, la plus commune étant la notation infixe \(x+y\). On peut également utiliser la notation préfixe où l'opérateur est placé cette fois avant les opérandes, notation généralement employée pour les fonctions, ici \(+\,(x,y)\); et aussi la notation postfixe \((x,y)\,+\) moins courante. Cette notation postfixe peut aussi être employée pour un opérateur unaire.

En s'appuyant sur cette dernière notation, une autre méthode permet d'évaluer une expression ari­thmé­ti­que ou logique, elle consiste à :

  1. réécrire l'expression infixe avec une notation postfixe, parfois appelée notation polonaise inverse, qui consiste à placer l'opérateur binaire après ses opérandes,
  2. évaluer l'expression postfixée à l'aide d'une pile, ce qui peut être réalisé de manière élémentaire.

La première étape est effectuée par l'algorithme de la Voie de triage développé par Dijkstra et qui sera étudié en troisième année. Nous nous intéressons ici à la deuxième étape qui se résume donc à évaluer une expression postfixe. Notons qu'il est tout à fait possible de se dispenser de la première étape, il suffit de calculer directement avec des expressions sous forme postfixe, ce qui ne pose aucun problème une fois familiarisé avec cette notation.

En notant \(a,b,\diamond\) plutôt que \((a,b)\diamond\) une opération binaire \(a\diamond b\), et \(a,\star\) une opération unaire \(\star a\), l'expression saisie plus haut devient :

L'absence des parenthèses est bien sûr déroutante et à première vue, on ne sait pas comment cette nouvelle expression va pouvoir être évaluée. On utilise pour cela une pile initialement vide. On lit suc­ces­si­ve­ment chacun des termes de l'expression et on applique l'une des trois règles suivantes selon la nature de ce terme :

  1. C'est un opérande, on l'empile.
  2. C'est un opérateur binaire \(\diamond\), 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. 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 est bien formée, à la fin de l'analyse, la pile ne doit plus con­te­nir que le résultat de l'évaluation (en orange) :

Évolution de la pile lors de l'évaluation de l'ex­pres­sion postfixe.

Certaines calculatrices utilisent toujours cette notation (comme la hp 15c en particulier, cf. mon ex­emp­lai­re personnel de 1982 dans la figure ci-dessous), la valeur affichée à l'écran est celle qui est au sommet de la pile et 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. Notez que cette calculatrice ne contient pas de touche \(=\).

Calculatrice HP 15c. La touche enter permet d'em­pi­ler les valeurs.

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

  1. Les parenthèses deviennent inutiles ;
  2. Les résultats 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.

Il y a quelques inconvénients, l'opérateur binaire de soustraction est distingué de l'opérateur unaire de négation (touche chs 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 ~ 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.
Donnez une version postfixée des expressions suivantes : \begin{align*} E=&2+3\\ E=&2(3-5)\\ E=&(2+3)(4-1)\\ E=&2(3-1)+[3(1+2(3-1))]-1\\ E=&-2+(3+1+2+1)(3-2) \end{align*} nb. Vous pouvez utiliser le programme d'évaluation plus haut pour vérifier que votre expression est cor­recte.

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.

ÉvaluerPF(expr):valeur
données
   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   
   RETOURNER 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).\]

Travaux pratiques

Tous les programmes et fonctions sont à écrire en langage C. Une fois compilé, votre programme devra récupérer les arguments de la ligne de commande (autant que de jetons) et renvoyer le résultat de l'évaluation. Par exemple
EVALUER 2.25 3 _ −
devra renvoyer
5.2500
Les paramètres codant en postfixe l'expression infixe \(2.25 - (-3)\).
Déclarez un type TJETON (structure) avec trois champss :
  1. Un flottant nombre pour coder un réel.
  2. Un caractère op pour coder un opérateur binaire parmi \(\{+,-,\times,/\}\) ou l'opérateur unaire \(\underline{\ \ }\) codant le changement de signe.
  3. Un type énuméré type pour coder le type du jeton (opérateur unaire, opérateur binaire, nombre). Selon le type d'un jeton, seul l'un de ses deux champs nombre ou op sera utilisé.
Déclarez un type TCELL pour coder une cellule d'une liste chaînée et un type TLISTE pointant vers un TCELL pour désigner une liste chaînée.
Écrivez la fonction TJETON Chaine2Jeton(char *chaine) qui convertit une chaîne en jeton et la fonction TEXPR Arg2Expr(char *arguments[], int n) qui convertit le tableau d'arguments en tableau de jetons.
Écrivez la fonction TPILE Empiler(TPILE pile, float nombre) qui empile le nombre en paramètre au sommet de la pile et renvoie cette nouvelle pile. CÉcrivez la fonction TPILE Depiler(TPILE pile, float *nombre) qui récupère le nombre au sommet de la pile, élimine la cellule correspondante en libérant l'espace mémoire et renvoie la pile ainsi mise à jour. Le nombre est récupéré par le passage par adresse.
Écrivez la fonction void AfficherPile(TPILE pile) qui affiche le contenu de la pile (horizontalement) sur le terminal (cela vous sera utile pour vérifier votre programme).
Écrivez la fonction float Operer(float x, float y, char op) qui renvoie le résultat de l'opération (x op y) si op est un opérateur binaire (addition +, soustraction −, multiplication ×, division /) et (op x) s'il s'agit d'un opérateur unaire (changement de signe >_ ).
Écrivez la fonction float Evaluer(TEXPR expr, uint n) qui evalue l'expression passée en paramètre (n est la taille de cette expression) et renvoie le résultat de l'évaluation.