Algorithmique ii - Évaluation avec une pile

Présentation du problème

On souhaite évaluer une expression arithmétique (ou logique), par exemple l'expression \begin{equation}\label{eq:expr} \color{#FFF}1.2\times(8-3)\times 3 + ((3-1)\times 2)\times 3. \end{equation} 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 de construction, suite de chiffres pour un entier, suite de chiffres contenant éventullement un point pour les nombres réels, symbole unique \(+,\times,-,/\) pour les opérateurs arithmétiques, etc. L'expression (\ref{eq:expr}) fournit la liste de jetons suivante :

1.2 × ( 8 3 ) × 3 + ( ( 3 1 ) × 2 ) × 3
Segmentation de l'expression \((\ref{eq:expr})\) 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 un opérande est lui même un expression, comme dans \(1.2\times(8-3)\) où \(8-3\) est l'opérande droit de l'opérateur binaire \(\times\), la feuille droite de l'arbre binaire associé est remplacée par le sous-arbre représentant l'expression \(8-3\). On obtient l'arbre de dérivation suivant pour l'expression (\ref{eq:expr}) (les parenthèses ont été omises, elles ne sont plus nécessaires)  :

Arbre de dérivation de l'expression arithmétique \((\ref{eq:expr})\).

Cet arbre est ensuite traité par un algorithme récursif. Si sa racine contient une valeur (dans ce cas, l'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 en notation infixe où les opérateurs binaires sont placés entre leurs opérandes est donc un problème absolument non trivial.

La notation postfixe, parfois appelée notation polonaise inverse, qui consiste à placer l'opérateur binaire après ses opérandes, associée à l'utilisation d'une pile vont permettre de résoudre ce pro­blè­me de manière quasi élémentaire. En notant \((a,b)\star\) ou \([a,b]\star\) une opération binaire \(a\star b\), l'expression arithmétique (\ref{eq:expr}) s'écrit : \begin{equation} {\color{#FF0}\Big[}{\color{#4F6}\big(}[1.2,(8,3)-]\times,3{\color{#4F6}\big)\!\times}\ ,\ {\color{#46F}\big(}[(3,1)-,2]\times,3{\color{#46F}\big)\!\times}{\color{#FF0}\Big]+} \end{equation} La structure arborescente de l'expression est mise en évidence ci-dessous en rem­pla­çant les pa­ren­thè­ses dans \((a,b)\star\) par une boite \(\boxed{a,b}\star\) : \begin{equation} \boxed{ \boxed{\boxed{1.2,\boxed{8,3}-}\times,3}\times, \boxed{\boxed{\boxed{\boxed{3,1}-,2}\times,3}}\times }+ \end{equation}

L'expression ne semble pas avoir gagné en simplicité, bien au contraire. Mais ce n'est qu'une apparence. Éliminons les parenthèses pour obtenir la simple liste constituée des opérandes et des opérateurs : \begin{equation} L:=(\color{#FFF}1.2,\ 8,\ 3,\ -,\ \times,\ 3,\ \times,\ 3,\ 1,\ -,\ 2,\ \times,\ 3,\ \times,\ +) \end{equation}

Pour évaluer cette dernière expression, on utilise une pile initialement vide. On lit successivement chacun des termes de l'expression et on applique l'une des deux règles suivante :

  1. Si le terme est un opérande, on l'empile.
  2. Si le terme est un opérateur \(\star\), on dépile successivement les deux valeurs au sommet de la pile \(y\) et \(x\), puis on empile \(x\star y\).
\(L =\ (\)\()\).

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. Vous pouvez saisir une expression sous forme postfixe quelconque pour analyser le processus, séparez les termes par un espace ou une virgule. Si l'expression est bien formée, à la fin de l'analyse, la pile ne doit plus contenir que le résultat de l'évaluation (en jaune) :

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

Certaines calculatrices utilisent toujours cette notation (comme la HP15c en particulier, cf. mon exemplaire 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, puisque l'opérateur doit suivre l'opérande, on écrit alors \(7.02\ \)neg pour calculer l'opposé du nombre \(7.02\). D'autre part, la gymnastique d'esprit à acquérir pour transformer men­ta­le­ment une expression en notation infixe en notation 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 Évaluer s'en déduit directement et calque les règles 1 et 2 plus haut :

Évaluer(expr):valeur
données
   expr: liste de jetons
variables
   i: entier
   pile: liste
debut    
   i ← 1
   pile ← ∅
   TQ (i ≤ #expr) FAIRE
      SI EstNombre(expr[i]) ALORS
         Empiler(pile,expr[i])
      SINON
         y ← Depiler(pile)
         x ← Depiler(pile)
         z ← Operation(expr[i],x,y)
         Empiler(pile,z)
      FSI
      i ← i + 1
   FTQ   
   RETOURNER Depiler(pile)
 FIN
Écrivez un algorithme de conversion qui transforme une expression sous forme infixe en une expression postfixe. Un premier algorithme devra transformer au préalable l'expression d'entrée en liste de jetons qui sera ensuite traitée par l'algorithme de conversion.

Indication : l'algorithme de conversion utilise une liste de sortie dans laquelle les jetons seront placés, et une pile. Il ajoute les jetons de type nombre dans la liste des jetons en sortie initialement vide, et les opérateurs sur la pile. Une fois la lecture achevée on dépile tous les opérateurs de la pile dans la liste de sortie. Par exemple l'expression \(1.02+2\) est décomposée en trois jetons \(1.02\), \(+\) et \(2\). Le premier jeton \(1.02\) est placé dans la liste des jetons de sortie, l'opérateur \(+\) est empilé, le jeton \(2\) est ajouté à la liste de sortie et tous les éléments de la pile sont dépilés et rajoutés à la liste de sortie pour obtenir \(1.02,2,+\).

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

Écrivez une fonction Python EstNombre(chaine) qui renvoie True si la chaîne de caractères en entrée est un nombre (flottant ou entier), False sinon. Vous analyserez la chaîne de caractère en entrée pas à pas et vous définirez une liste de chiffres.

Écrivez une fonction Python PostFixe(expr) qui évalue une expression postfixée (une liste) à l'aide d'une pile. On supposera que les opérandes sont uniquement des nombres flottants ou entiers et que les opérateurs se limitent aux quatre opérations arithmétiques +, −, × ÷

Indications: en Python, on empile un élément x au sommet d'une pile P (une liste) avec P.append(x) et on dépile avec x = P.pop()