Évaluation d'une expression postfixe

Nous avons l'habitude de noter les expressions arithmétiques avec des parenthèses comme : \((2 + 3) \times 5\).

Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n'utilise pas de parenthèses. L'expression arithmétique précédente est alors obtenue en saisissant successivement \(2\), puis \(3\), puis l'opérateur \(+\), puis \(5\), et enfin l'opérateur \(\times\).

On modélise cette saisie par la liste Python [2, 3, '+', 5, '*'].

De la même façon, la notation postfixe de \(3 \times 2 + 5\) est modélisée par la liste [3, 2, '*', 5, '+'].

L'évaluation (le calcul) d'une expression arithmétique en notation postfixe peut s'obtenir à l'aide d'une pile en parcourant l'expression arithmétique de gauche à droite de la façon suivante :

• Si l'élément lu est un nombre, on le place au sommet de la pile.
• Si c'est un opérateur, on récupère les deux valeurs situées au sommet de la pile et on leur applique l'opération. On place le résultat au sommet de la pile.
• À la fin du parcours, il reste un seul élément dans la pile : c'est le résultat de l'expression arithmétique.

Dans le cadre de cet exercice, on se limitera aux opérations \(\times\) et \(+\). On garantit de plus que l'expression est "bien formée", c'est-à-dire que l'expression arithmétique a du sens (\(3 \times 2\) a du sens, pas \(3\;+\;\times\)).

Pour cet exercice, on dispose d'une classe Pile qui implémente les méthodes de base sur la structure de pile.

Compléter le script de la fonction evaluation_postfixe qui :

• prend en paramètre une liste Python représentant la notation postfixe d'une expression arithmétique,

• renvoie sa valeur associée.

Exemples

🐍 Console Python

>>> evaluation_postfixe([3, 2, '*', 5, '+']) # correspond à 3 * 2 + 5
11
>>> evaluation_postfixe([2, 3, '+', 5, '*']) # correspond à (2 + 3) * 5
25
>>> evaluation_postfixe([2]) # correspond à 2
2
>>> evaluation_postfixe([2, 3, 4, '*', '*']) # correspond à 4 * 3 * 2
24

Question

###

Lancer # Testsbksl-nlassert evaluationpy-undpostfixe([3, 2, 'py-str', 5, '+']) == 11bksl-nlassert evaluationpy-undpostfixe([2, 3, '+', 5, 'py-str']) == 25bksl-nlassert evaluationpy-undpostfixe([2]) == 2bksl-nlassert evaluationpy-undpostfixe([2, 3, 4, 'py-str', 'py-str']) == 24bksl-nlbksl-nl# Tests supplémentairesbksl-nlassert evaluationpy-undpostfixe([3, 2, 5, '+', '+']) == 10bksl-nlassert evaluationpy-undpostfixe([100, 3, 'py-str', 5, 'py-str']) == 1500bksl-nlassert evaluationpy-undpostfixe([0]) == 0bksl-nlassert evaluationpy-undpostfixe(list(range(1, 11))+['+']py-str9) == 55bksl-nlassert evaluationpy-undpostfixe(list(range(1, 11))+['py-str']py-str9) == 3py-und628py-und800bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

class Pile:bksl-nl """Classe définissant une structure de pile."""bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = []bksl-nlbksl-nl def estpy-undvide(self):bksl-nl """Renvoie le booléen True si la pile est vide, False sinon."""bksl-nl return self.contenu == []bksl-nlbksl-nl def empiler(self, element):bksl-nl """Place element au sommet de la pile"""bksl-nl self.contenu.append(element)bksl-nlbksl-nl def depiler(self):bksl-nl """bksl-nl Retire et renvoie l'élément placé au sommet de la pile,bksl-nl si la pile n'est pas vide.bksl-nl """bksl-nl if not self.estpy-undvide():bksl-nl return self.contenu.pop()bksl-nlbksl-nldef evaluationpy-undpostfixe(expression) :bksl-nl pile = Pile()bksl-nl for element in expression :bksl-nl if element != '+' ... element != '...':bksl-nl pile.empiler(...)bksl-nl else :bksl-nl if element == ...:bksl-nl resultat = pile.depiler() + ...bksl-nl else:bksl-nl resultat = ...bksl-nl pile.empiler(...)bksl-nl return ...bksl-nlbksl-nl# Testsbksl-nlassert evaluationpy-undpostfixe([3, 2, 'py-str', 5, '+']) == 11bksl-nlassert evaluationpy-undpostfixe([2, 3, '+', 5, 'py-str']) == 25bksl-nlassert evaluationpy-undpostfixe([2]) == 2bksl-nlassert evaluationpy-undpostfixe([2, 3, 4, 'py-str', 'py-str']) == 24bksl-nlbksl-nlbksl-nldef evaluationpy-undpostfixe(expression):bksl-nl pile = Pile()bksl-nl for element in expression:bksl-nl if element != '+' and element != 'py-str':bksl-nl pile.empiler(element)bksl-nl else:bksl-nl if element == '+':bksl-nl resultat = pile.depiler() + pile.depiler()bksl-nl else:bksl-nl resultat = pile.depiler() py-str pile.depiler()bksl-nl pile.empiler(resultat)bksl-nl return pile.depiler()bksl-nl bksl-nl

---

La démarche

On suit pas à pas la démarche présentée dans l'énoncé.

Un élément du tableau est un nombre si ce n'est ni l'opérateur \(+\) ni \(\times\). On teste donc if element != '+' and element != '*':.

Dans le cas où élément est un opérateur, on traite séparément chaque cas (+ et *). À chaque fois on dépile les deux premiers nombres de la pile et on effectue l'opération. On empile le résultat.

À la fin du parcours, l'expression étant bien formée, il ne reste qu'une valeur dans la pile : le résultat de l'évaluation que l'on dépile et renvoie immédiatement.

---