TP - Pile

La notation polonaise inverse (NPI), également connue sous le nom de notation post-fixée, permet d'écrire de façon non ambiguë les formules arithmétiques sans utiliser de parenthèses. Dérivée de la notation polonaise présentée en 1924 par le mathématicien polonais Jan Łukasiewicz, elle s'en différencie par l'ordre des termes, les opérandes y étant présentés avant les opérateurs et non l'inverse.

Par exemple, l'expression
(4 + 5) × 6
peut s'écrire en NPI sous la forme
4 5 + 6 ×
ou encore sous la forme
6 4 5 + ×

Le but de l'exercice est de réaliser en python une calculatrice simple, capable d'évaluer une formule en NPI et de retourner le résultat arithmétique. La réalisation d'une telle calculatrice se fera à l'aide d'une pile.

L'algorithme pour évaluer une formule en NPI se déroule de la manière suivante:

• on parcours les caractère de la formule de gauche à droite
• si le caractère lu est un opérande (par exemple un un entier): on l'empile
• si le caractère lu est un opérateur (par exemple la multiplication): on calcule le résultat de l'application de l'opérateur sur les deux opérandes au sommet de la pile, et on l'empile
• lorsque tout les caractères de la formule sont lus: on lit le résultat au sommet de la pile (qui ne contient d'ailleurs plus qu'un élément)

Par exemple, voici les différents états successifs de la pile à la lecture de chaque caractère de l'expression 4 5 + 6 ×

On peut vérifier que le sommet de la pile dans l'état final correspond bien au résultat de
(4 + 5) × 6 = 54

À vous de jouer

Écrire le programme qui permet d'évaluer une expression qu'on modélisera par un tableau de la forme expr = ['4', '5', '+', '6', '*']. Les caractères autorisés sont les entiers de 1 à 9 pour les opérandes et les 4 opérateurs suivants: $(+, -, /, *)$

1. Écrire la fonction est_operateur(c: str) qui prend en entrée un caractère et renvoie True s'il s'agit d'un opérateur, False sinon. On peut avoir besoin de la fonction c.isdigit() (attention, ne fonctionne que sur des str).

2. Écrire la fonction calcul(op: str, a: int, b: int) qui prend en paramètre un opérateur op parmis les 4 autorisés, et deux entiers a et b. Elle renvoie le résultat du calcul: a op b.

Avec une pile

On fournit dans un fichier pile.py des primitives de pile qu'il suffira d'importer en incluant la ligne en début de fichier:

from pile import *

Ces primitives sont les suivantes:

pile_cree()                 # renvoie une pile
pile_taille(pile)           # renvoie la hauteur de la pile
pile_est_vide(pile)         # renvoie True si vide, False sinon
pile_empiler(pile, element) # rajoute element au sommet de la pile
pile_depiler(pile)          # enleve un element au sommet et le renvoie
pile_sommet(pile)           # renvoie le sommet de la pile

3. Écrire la fonction evaluation(expr: list) qui prend en paramètre une expression sous la forme d'un tableau de caractère correspondant à une formule en NPI. Elle renvoie le résultat du calcul de l'expression en utilisant les primitives de pile importées.

Remarque: Pour transformer un entier sous forme de chaine de caractère en véritable entier python on peut utiliser int(c: str) comme dans l'exemple ci-dessous.

>>> c
'3'
>>> int(c)
3

Implémentation "maison" de la pile

4. Réécrire les fonctions correspondants aux primitives de pile en stockant les éléments dans un tableau python. Ci-dessous des indications pour "traduire" un tableau en pile.

Indications:

• pile_maison_cree(): on peut se contenter de renvoyer un simple tableau vide
• pile_maison_taille(pile: list): le nombre d'élément dans le tableau
• pile_maison_est_vide(pile: list): le tableau est-il vide?
• pile_maison_empiler(pile: list, element): rajouter l'élément à la fin ou au début du tableau
• pile_maison_depiler(pile: list): accéder au dernier élément inséré non supprimé, et le supprimer du tableau
• pile_maison_sommet(pile: list): accéder au dernier élément inséré non supprimé

Pour aller plus loin

5. Écrire un programme interactif qui demande à l'utilisateur une expression en NPI en utilisant input() et en affiche le résultat. Traiter notamment les cas particuliers de syntaxe: on peut imaginer accepter les formules NPI avec ou sans espaces, prévenir l'utilisateur en cas d'erreur de syntaxe NPI, etc.