Livre_silo 30 août 2013 16:32 Page 309
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
309
12 – Structure de pile
courant est un opérateur, on dépile les deux opérandes, on effectue le calcul et on empile
le résultat.
La solution que l’on propose ici fait l’hypothèse que les expressions arithmétiques
contiennent uniquement les opérateurs + et ∗. Il est très facile de l’étendre à d’autres
opérateurs.
On commence donc par créer une pile p :
def eval_npi(exp):
p = creer_pile(len(exp))
La capacité maximale de la pile est ici la longueur de l’expression arithmétique len(exp),
puisqu’on ne va pas empiler plus de nombres que ceux contenus dans le tableau. On parcourt alors tous les éléments du tableau exp, de la gauche vers la droite, avec une boucle for :
for c in exp:
Si l’élément courant c est un opérateur arithmétique (caractère '+' ou '*'), on dépile les
deux opérandes x et y de p et on empile x + y ou x * y, selon la valeur de c :
if c == '+' or c == '*':
y = depiler(p)
x = depiler(p)
empiler(p, x + y if c == '+' else x * y)
Sinon, c est un nombre et on l’empile dans p :
else:
empiler(p, c)
Quand on sort de la boucle for, il ne reste plus qu’à dépiler la valeur finale v de l’expression
et à vérifier que la pile p est bien vide :
v = depiler(p)
assert est_vide(p)
return v
Le code complet est donné ci-après.
PROGRAMME 14 Évaluation d’une expression en notation polonaise inverse
def eval_npi(exp):
p = creer_pile(len(exp))
for c in exp:
if c == '+' or c == '*':
y = depiler(p)
x = depiler(p)
empiler(p, x + y if c == '+' else x * y)
else:
empiler(p, c)
v = depiler(p)
assert est_vide(p)
return v