Ecole d’Ingénieurs du Littoral Côte d’Opale
Algorithmique avancée et programmation
TP4 (Pile et File)
Exercice 1 :
Question 1
Nous voulons développer un ensemble de fonctions pour manipuler une pile de nombres
réels. L’implémentation de ces fonctions est dans les fichiers pile.h et pile.c. On choisit
de représenter la pile avec une liste linéaire chainée simple.
Question 2
La notation postfixe est une façon d’écrire des expressions mathématiques sans devoir
mettre de paranthèses. Par exemple, pour l’expression arithmétique (3+5)∗4 la notation
postfixe sera 35 + 4∗. Pour evaluer une telle expression, on applique le principe suivant :
— parcourir l’expression arithmétique
— empiler les entiers que l’on rencontre
— lorsque l’on rencontre un opérateur, il nous faut :
— dépiler les 2 derniers entiers
— leur appliquer l’opérateur
— empiler le résultat ;
— une fois le parcours terminé, le résultat du calcul devrait être dépilé et retourné
Ecrire la fonction float evaluer(char expression []) qui calcule le résultat d’une ex-
pression arithmétique postfixe. Pour faire simple, nous nous limitons aux chiffres comme
opérandes et aux opérateurs {+, −, ∗, /}.
Question 3
On va s’intéresser à des expressions complètement parenthésées comme, par exemple,
(((3+4)∗5)−6) ou (3+(4∗(5−6))). L’évaluation s’effectue en deux étapes. Tout d’abord
on procède à une conversion en écriture postfixe. Ensuite, on évalue cette dernière.
1
La conversion de l’écriture infixe complètement parenthésée en écriture postfixe se fait
à l’aide d’une pile d’opérateurs (pile de caractères) :
— les opérandes sont recopiés dans l’expression postfixe immédiatement,
— les opérateurs sont empilés au fur et à mesure de leur lecture,
— à chaque lecture d’une parenthèse fermante, on retire un opérateur de la pile et
on le recopie dans l’expression postfixe.
Compléter les fichiers P ileC.h et P ileC.c qui permettent de définir une pile de caractères
puis utiliser cette pile pour implémenter la fonction char * convertir infixe postfixe(char
expI[]) qui permet de convertir une expression arithmétique infixe complètement pa-
renthésée en une expression postfixe.
Question 4 :(bonus à faire en dehors de la séance TP)
On voudrait généraliser la fonction précédente pour convertir toute chaı̂ne arithmétique
(pas forcément parenthésée). Par exemple, l’expression 5 ∗ ((9 + 8) + (4 ∗ 6) + 7) s’écrit
en notation polonaise inversée 5 9 8 + 4 6 ∗ + 7 + ∗.
Pour réaliser cette fonction, on applique les principes suivants :
— une parenthèse ouvrante est directement empilée
— un chiffre est directement copié dans la chaı̂ne postfixe.
— si le caractère est un opérateur, l’action à effectuer dépend de ce que contient la
pile :
— si la pile est vide, l’opérateur est empilé
— sinon, on dépile les opérateurs de priorité supérieure qui se trouve en sommet
de pile et on les copie dans la chaı̂ne postfixe
— si le caractère est une parenthèse fermante, on dépile tous les opérateurs en som-
met de pile et on les copie dans la chaı̂ne postfixe. On s’arrête lorsqu’on rencontre
une parenthèse ouvrante (qu’on dépile sans la copier dans la chaı̂ne postfixe )
Ecrire la fonction char * convertir infixe postfixe generalisee(char expI[]) qui
permet de convertir une expression arithmétique infixe en une expression postfixe.
Exercice 2
Nous voulons simuler les arrivées de clients à un guichet de banque à l’aide d’une file.
Un client est défini par son identifiant, son temps d’arrivée et la durée de traitement de
sa demande.
— compléter les fichiers file.h et file.c qui définissent les fonctions de manipulation
d’une file de clients
— testez vos fonctions dans le main selon le scénario suivant
— créer une file avec 10 clients. Un client arrive chaque minute avec une demande
qui nécessite une durée de traitement aléatoire entre 5 à 10 minutes.
— calculer le temps d’attente moyen des clients dans cette file
