TD 10 - Piles
1 Les bases des piles
1.1 Exercice 1
Rappeler comment implémenter une pile à l’aide d’un tableau. Vous écrirez les algorithmes des 4 procédures standards utilisées.
Principe : Last In, First Out (dernier entré, premier sorti)
Opérations de base : - Empiler(P, x) : Ajouter x au sommet de la pile - Depiler(P) : Retirer et retourner l’élément au sommet - Lire(P) ou Sommet(P) : Consulter l’élément au sommet sans le retirer - EstVide(P) : Vérifier si la pile est vide
Implémentation par tableau : - Tableau de taille fixe (ou dynamique) - Un pointeur/indice sommet qui pointe vers le dernier élément
2 Parenthésage
2.1 Exercice 2
Écrire un algorithme qui retourne VRAI si une chaîne de caractères est correctement parenthésée et FAUX sinon. On considèrera non seulement les parenthèses classiques (), mais aussi les crochets [] et les accolades {}. Par exemple, pour l’entrée ()[()] l’algorithme retournera VRAI et pour {(}) il retournera FAUX.
- Parcourir la chaîne caractère par caractère
- Si c’est un ouvrant
(,[,{→ empiler - Si c’est un fermant
),],}:- Vérifier que la pile n’est pas vide
- Dépiler et vérifier que l’ouvrant correspond au fermant
- À la fin, la pile doit être vide
Exemples : - ()[()] ✓ (correct) - {(}) ✗ (mauvaise correspondance) - ((() ✗ (pile non vide à la fin) - ()) ✗ (pile vide lors d’un fermant)
3 NPI
3.1 Exercice 3 : Notation Polonaise Inverse
Les expressions arithmétiques sont traditionnellement écrites de manière infixe : l’opérateur est placé entre les deux opérandes. Il existe également une notation postfixée avec laquelle l’opérateur est placé après les opérandes. Par exemple \(3+14\) s’écrit \(3~14~+\) et \((2+5)\times 11\) s’écrit \(2~5~+~11~\times\). L’intérêt de cette notation est que l’on peut se passer de la priorité des opérateurs pour évaluer une expression.
Écrire un algorithme en \(\Theta(n)\) qui prend en entrée une expression arithmétique postfixée donnée sous la forme d’un tableau de \(n\) données représentant soit des nombres, soit des opérateurs et qui retourne son évaluation.
On pourra utiliser la fonction TYPE(x) qui renvoie NB ou OP selon que x est un nombre ou un opérateur et la fonction EVAL(a,b,op) qui retourne le résultat de l’expression a op b où a et b sont des nombres et op un opérateur.
Principe : 1. Parcourir l’expression de gauche à droite 2. Si c’est un nombre → empiler 3. Si c’est un opérateur : - Dépiler deux opérandes (b puis a) - Calculer a op b - Empiler le résultat 4. À la fin, le résultat est au sommet de la pile
Exemple : \(2~5~+~11~\times\) - Lire 2 → empiler → pile : [2] - Lire 5 → empiler → pile : [2, 5] - Lire + → dépiler 5 et 2, calculer 2+5=7, empiler → pile : [7] - Lire 11 → empiler → pile : [7, 11] - Lire × → dépiler 11 et 7, calculer 7×11=77, empiler → pile : [77] - Résultat : 77
4 En plus
4.1 Exercice 4 🏠
On considère dans la suite des piles contenant des nombres entiers.
On considère une pile \(P\) triée dans l’ordre croissant (le plus grand élément au sommet). Écrire un algorithme
InserePile(P,x)qui insère l’entier \(x\) à sa place dans la pile. L’algorithme ne pourra utiliser qu’une seule autre pile en variable auxiliaire (en plus d’éventuelles variables entières).En déduire un algorithme
TriPile(P1,P2), basé sur l’algorithme du tri insertion, qui range les éléments de la pile \(P1\) dans la pile \(P2\) dans l’ordre croissant. L’algorithme ne pourra pas utiliser de pile auxiliaire mais pourra faire appel à la fonctionInserePile(P,x).En vous inspirant de l’algorithme
InserePile(P,x), écrire un algorithmeTriPile2(P1,P2), basé sur l’algorithme du tri insertion, qui range les éléments de la pile \(P1\) dans la pile \(P2\) dans l’ordre croissant. L’algorithme ne pourra pas utiliser de pile auxiliaire ni faire appel à la fonctionInserePile(P,x).
- InserePile : Dépiler les éléments plus grands dans la pile auxiliaire, empiler x, puis remettre les éléments
- TriPile : Dépiler chaque élément de P1 et l’insérer dans P2 (qui reste triée)
- TriPile2 : Intégrer le code d’insertion directement dans la boucle principale