TD — Piles et files

MP2I, année scolaire 2021/2022.

La plupart des exercices donnés ici peuvent être implémentés en OCaml ou en C, mais l'objectif premier est de réfléchir et d'en faire plus que si on le faisait en TP.

Rappel

Chacune des structures piles et files est caractérisée par deux opérations essentielles, ajouter et retirer un élément selon la stratégie suivante :

• Une pile est LIFO : Last In First Out. Le dernier élément ajouté est le premier qu'on retire.
• Une file est FIFO : First In First Out. Le premier élément ajouté est le premier qu'on retire.

Les opérations de création et de test si la structure est vide sont dans la suite supposées peu intéressantes. On se concentre sur ajouter/retirer.

Réalisation d'une file

Exercice 1. On souhaite réaliser une file avec une liste chaînée. Indiquer comment réaliser les opérations et leur complexité :

• avec des listes comme en OCaml ;
• en utilisant explicitement des maillons mais sans liste doublement chaînée.

Exercice 2. On souhaite maintenant réaliser une file avec un tableau de taille fixe. La stratégie va être de maintenir deux indices : le début et la fin de la file et de considérer que les bords du tableau se rejoignent.

Indiquer comment réaliser les opérations et leur complexité.

Exercice 3. Montrer qu'on peut réaliser efficacement une file avec deux piles et indiquer la complexité des opérations.

On en déduit une implémentation des files en OCaml avec deux références sur des listes.

Exercice 4. Montrer qu'on peut réaliser efficacement une pile avec deux files et indiquer la complexité des opérations.

Exercice 5. Montrer qu'on peut réaliser inefficacement une pile avec une file et indiquer la complexité des opérations.

Algorithme de Dijkstra pour l'évaluation d'expressions

On a vu comment évaluer une expression postfixe avec une pile, Dijkstra a trouvé un algorithme utilisant deux piles pour évaluer une expression infixe, c'est-à-dire une expression standard avec des parenthèses \((1+(2\times 3)-(3\times 4))-2\).

On considère deux piles, une pile de nombres et une pile d'opérateurs.

Pour chaque symbole :

• Si c'est une parenthèse ouvrante, on l'ignore ;
• Si c'est un nombre on le pousse sur la pile de nombres ;
• Si c'est un opérateur on le pousse sur la pile d'opérateurs ;

• Si c'est une parenthèse fermante, on dépile un opérateur et autant de nombres que son arité (son nombre d'opérandes), puis on empile le résultat.

• Évaluer ainsi \((1+((2+3)\times (4\times 5)))\).

• Justifier que la méthode fonctionne.
• En déduire une conversion en notation postfixe.

Sous-chaîne parenthésée

On considère ici le problème des expressions bien parenthésées dans le contexte simple où il n'y a que deux caractères '(' et ')'. Une chaîne est donc de la forme (()(( ou (()(())) et on considère qu'elle est sous la forme d'un tableau de caractères.

On a vu qu'on pouvait vérifier si la chaîne était bien parenthésée avec un entier.

On cherche une sous-chaîne bien parenthésée de longueur maximale, c'est-à-dire un sous-tableau entre les indices \(i\) et \(j\) bien parenthésé et tel que \(j-i+1\) soit maximal. Votre algorithme doit être de complexité \(O(n)\) où \(n\) est la longueur initiale de la chaîne.

On vous demande également de prouver que votre algorithme est correct.