Université des Sciences et Technologies de Lille
Licence Miage - Programmation 1 - TP
Expressions postfixées
1ère partie : un paquetage pile
Une pile est un modèle de données représentant des listes d'objets,
pour lesquelles on dispose de deux opérations élémentaires :
empiler un élément en haut de la pile ou bien
dépiler un élément de la pile, i.e. enlever l'élément qui est en tête
de la pile.
Une manière d'implémenter une pile en ADA est de définir un type
enregistrement avec un discriminant pour la taille maximale de la pile.
C'est ce qui vous est proposé dans la spécification du paquetage
Paq_Pile, qui se trouve dans
~touzet/ADA/Piles/paq_pile.ads
Écrire le corps du paquetage.
2ème partie : application à l'évaluation d'une
expression postfixée
Nous considérons les expressions arithmétiques
formées de nombres naturels et des opérateurs + et *.
Ces expressions acceptent plusieurs représentations.
La notation usuelle, comme (3+5)* 2, est dite infixée. Son
défaut est de nécessiter l'utilisation de parenthèses pour éviter toute
ambiguité. Cela permet de distinguer 3+(5 * 2)
de (3+5)* 2. Pour éviter le parenthésage, il est possible de
transformer une expression infixée en une expression postfixée : on
fait glisser les opérateurs arithmétiques à la suite des
expressions auxquelles ils s'appliquent.
| exp1 + exp2 |
Þ |
exp1 exp2 + |
| exp1 * exp2 |
Þ |
exp1 exp2 * |
Par exemple, l'écriture postfixée de (3+5) * 2 est 3 5 +
2 * et celle de 3+(5 * 2) est 3 5 2 * +.
Comment se fait l'évaluation d'une expression postfixée? À
l'aide d'une pile d'entiers... On
part d'une pile vide, puis on parcourt l'expression en actualisant la
pile ainsi:
-
on lit un nombre : on l'empile,
- on lit + : on dépile les deux éléments de tête, on
effectue la somme, et on empile le résultat,
- on lit * : on dépile les deux éléments de tête, on
effectue le produit, puis on empile le résultat.
À la fin, la pile doit être réduite à un seul élément, qui contient le résultat.
L'évaluation s'est ainsi faite en temps linéaire.
Exemple : 3 5 + 7 12 + * 3 +
| |
|
|
|
12 |
|
|
|
|
| |
5 |
|
7 |
7 |
19 |
|
3 |
| 3 |
3 |
8 |
8 |
8 |
8 |
152 |
152 |
155 |
| 3 |
5 |
+ |
7 |
12 |
+ |
* |
3 |
+ |
Le résultat est 155.
Écrire un programme qui permet l'évaluation d'une expression
postfixée lue dans une chaîne de caractères.