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 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'évaluation.
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 correspondante a du sens ([2,3,'+',5,'*'] correspond à \((2 + 3) \times 5\) et a du sens, [2,3,'+','*'] correspond à \((2 + 3) \times\) et n'a pas de sens).
Pour cet exercice, on dispose d'une classe Pile qui implémente les méthodes de base sur la structure de pile. Cette classe est déjà chargée dans l'éditeur, vous pouvez l'utiliser directement.
Interface de la classe Pile
p = Pile() : crée une pile vide et l'affecte à la variable p;
p.est_vide() : renvoie le booléen indiquant si la pile p est vide ;
p.empile(x) : empile l'élément x dans la pile p;
p.depile() : dépile un élément de la pile p si elle n'est pas vide et le renvoie. Provoque une erreur si la pile est vide.
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
>>> evaluation_postfixe([3,2,'*',5,'+'])# correspond à 3 * 2 + 511>>> evaluation_postfixe([2,3,'+',5,'*'])# correspond à (2 + 3) * 525>>> evaluation_postfixe([2])# correspond à 22>>> evaluation_postfixe([2,3,4,'*','*'])# correspond à 2 * 3 * 424
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)