Université Ibn Tofail
Ecole Supérieure de Technologie
Kénitra
Algorithmique Avancé et Structures de Données Abstraites
DUT / Génie Informatique (S2)
TP N° 6 : Les Piles
(Evaluation d’une expression arithmétique)
Une expression arithmétique est un ensemble d’opérandes reliés par des operateurs. L’écriture
habituelle des expressions arithmétique est appelée notation infixée, par la suite on s'intéresse
à des expressions infixées complètement parenthèsées comme, par exemple,
(((3+4)*8)-6) ou (3+(4*(8-6)))
L'évaluation d’une expression en notation infixée peut se faire en deux étapes.
- Conversion en écriture postfixée.
- Evaluation de l’expression postfixée.
Conversion en notation Postfixe
Une expression peut être représentée par une chaine de caractères :
Exemple : l’expression (3+(4*(8-6))) est représentée comme suit :
( 3 + ( 4 * ( 8 – 6 ) ) ) \0
On considère une chaine de caractères expInf représentant une expression, la conversion de
cette écriture en écriture postfixée se fait à l'aide d'une pile d'opérateurs selon les étapes
suivantes:
• Création d’une chaine vide expPost
• Création d’une Pile d’éléments de type caractère
• Parcourir l’expression expInf
o Si on rencontre une parenthèse ouvrante '(', on ne fait rien
o Si c’est un opérande il est recopié directement dans la chaine expPost.
o Si c’est un operateur (+, -, *, / ou %) il est empilé.
o à chaque lecture d'une parenthèse fermante ')', on retire un opérateur de la pile
et on le recopie dans expPost.
A la fin du parcours, la chaine expPost contient la notation postfixée de l’expression expInf.
Exemple :
Si expInf=(3+(4*(8-6))) alors expPost = 3 4 8 6 - * +
Evaluation de l’expression postfixée
Pour simplifier, on se limite aux opérandes entiers compris entre 0 et 9, et pour limiter les
problèmes d'arithmétique, on n'utilisera que les opérateurs +, -, * et /.
La notation postfixée s'évalue très simplement à l'aide d'une pile d'opérandes :
- les opérandes sont empilés au fur et à mesure de leur lecture
Pr. Moulay Youssef Hadi 1/2 DUT / GI S4)
Université Ibn Tofail
Ecole Supérieure de Technologie
Kénitra
- les opérateurs s'appliquent immédiatement en retirant les deux opérandes situés au
sommet de la pile et en y replaçant le résultat.
- le résultat final est la seule valeur qui reste dans la pile.
Exemple : l'évaluation de « 3 4 8 6 - * + » donne 11
L’expression 3 4 8 6 - * +
L’état de la pile 8 8 2
4 4 4 4 8
3 3 3 3 3 3 11
Et l’évaluation de 3 4 + 8 * 6 - (en notation infixée (((3+4)*8)-6)) donne 50.
Travail à faire :
- Définir la structure d’une pile des opérandes PileOpd.
- Ecrire la fonction d’entête void initPileOpd(PileOpd & adrP) qui permet
d’initialiser une pile vide d’opérandes d’adresse adrP.
- Ecrire la fonction d’entête void empilerOpd(PileOpd * adrP, int x) qui
permet d’ajouter un élément x dans la pile d’adresse adrP.
- Ecrire la fonction d’entête int depilerOpd(PileOpd * adrP) qui permet de retirer
et retourner le sommet de la pile.
- Refaire les questions précédentes avec une pile des operateurs PileOpr (il faut changer
les noms de fonctions)
- Ecrire la fonction char * convertirInf2Post(char * expInf) qui prend en
paramètre une expression en notation infixée et retourne sa conversion en notation
postfixée.
- Ecrire la fonction int calculer(int x, int y, char op) qui prend en paramètre
deux opérandes x et y et un opérateur op sous forme de caractère pour calculer
l’expression x op y :
Exemple : l’appel calculer(3,7,'+') retournera la valeur 10.
- Ecrire la fonction int evaluer(char * exp) qui prend en paramètre une expression
postfixée et retourne un entier qui est le résultat de l’évaluation de exp, pour cela :
o Convertir exp en une notation postfixée expPost
o Créer une pile vide des entiers pour empiler/dépiler les opérandes.
o Parcourir expPost en l’évaluant suivant la procédure décrite ci-dessus.
o Retourner le résultat
- Ecrire la fonction principale main() qui permet de :
o Déclarer et lire une expression infixée complètement parenthèsée expInf,
o Evaluer expInf.
N.B. :
- int isdigit(int C) : retourne une valeur différente de zéro, si C est un chiffre
décimal (ctype.h).
- int atoi(const char *CH) : retourne la valeur numérique représentée par CH
comme int (stdlib.h).
Pr. Moulay Youssef Hadi 2/2 DUT / GI S4)
