Piles et files : exercices corrigés de Terminale NSI

Après empiler(4) puis empiler(7) : la pile vaut [4, 7], sommet à droite.

Premier depiler() : il renvoie 7, la pile vaut [4].

empiler(2) puis empiler(9) : la pile vaut [4, 2, 9].

Deuxième depiler() : il renvoie 9, la pile vaut [4, 2]. Troisième depiler() : il renvoie 2, la pile vaut [4].

Les valeurs renvoyées sont donc 7, 9, 2 et la pile finale est [4].

Somme des valeurs dépilées : 7 + 9 + 2 = 18.

Après trois enfiler : la file vaut [5, 8, 3], la tête est 5.

Premier defiler() : il renvoie 5, la file vaut [8, 3].

enfiler(6) : la file vaut [8, 3, 6].

Deuxième defiler() : il renvoie 8, la file vaut [3, 6].

Les valeurs renvoyées sont 5 puis 8, dans l'ordre d'arrivée, et la file finale est [3, 6].

Somme des éléments restants : 3 + 6 = 9.

Situation 1 : l'action à défaire est toujours la dernière effectuée, donc c'est le plus récent qui sort en premier. Il faut une pile.

Situation 2 : le premier document envoyé doit être le premier imprimé. Il faut une file.

Situation 3 : la parenthèse fermante se compare à la dernière ouvrante non fermée, donc à la plus récente. Il faut une pile.

Situation 4 : le premier client arrivé est servi en premier, ce qui est le fonctionnement type d'une file ². Il faut une file.

On stocke les éléments dans un attribut contenu, liste initialement vide. L'ajout et le retrait se font à la fin de la liste, donc à coût faible.

est_vide renvoie len(self.contenu) == 0.

empiler appelle self.contenu.append(x).

depiler vérifie d'abord est_vide, lève IndexError avec un message si besoin, sinon renvoie self.contenu.pop().

Pour inverser, on empile chaque élément de la liste, puis on dépile jusqu'à ce que la pile soit vide en ajoutant chaque valeur à la liste résultat. Le dernier empilé sort le premier : l'ordre est renversé.

Code complet :

class Pile:
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        return len(self.contenu) == 0

    def empiler(self, x):
        self.contenu.append(x)

    def depiler(self):
        if self.est_vide():
            raise IndexError("pile vide")
        return self.contenu.pop()


def inverser(liste):
    p = Pile()
    for x in liste:
        p.empiler(x)
    resultat = []
    while not p.est_vide():
        resultat.append(p.depiler())
    return resultat

On définit un dictionnaire associant chaque fermant à son ouvrant : {")": "(", "]": "[", "}": "{"}.

On parcourt la chaîne. Un ouvrant est empilé.

Pour un fermant : si la pile est vide, la réponse est False ; sinon on dépile et on compare avec l'ouvrant associé, False en cas de différence.

À la fin du parcours, la chaîne est correcte si et seulement si la pile est vide.

Code :

def bien_parenthese(s):
    couples = {")": "(", "]": "[", "}": "{"}
    p = Pile()
    for c in s:
        if c in "([{":
            p.empiler(c)
        elif c in couples:
            if p.est_vide() or p.depiler() != couples[c]:
                return False
    return p.est_vide()

Trace sur "{[()]}" : on empile {, [, (. Le ) dépile ( : correct. Le ] dépile [ : correct. Le } dépile { : correct. La pile est vide, donc True.

Trace sur "([)]" : on empile ( puis [. Le ) dépile [, qui n'est pas ( : la fonction renvoie False aussitôt.

Après trois enfiler : entree = [1, 2, 3] (sommet à droite), sortie est vide.

Premier defiler() : sortie est vide, on transfère. On dépile 3, 2, 1 de entree et on les empile dans cet ordre : sortie = [3, 2, 1], sommet 1. Trois éléments déplacés. On dépile sortie : valeur renvoyée 1.

enfiler(4) : entree = [4], sortie = [3, 2].

Deuxième defiler() : sortie n'est pas vide, aucun transfert. Valeur renvoyée 2.

Troisième defiler() : valeur renvoyée 3, sortie est maintenant vide.

Quatrième defiler() : sortie est vide, on transfère l'élément 4 (un déplacement) puis on le dépile : valeur renvoyée 4.

Valeurs renvoyées : 1, 2, 3, 4, soit l'ordre d'arrivée. Déplacements : 3 + 1 = 4.

3 : pile [3]. 4 : pile [3, 4].

+ : on dépile 4 puis 3, on calcule 3 + 4 = 7, on empile : [7].

2 : pile [7, 2]. * : on dépile 2 puis 7, on calcule 7 × 2 = 14, on empile : [14].

7 : pile [14, 7]. - : on dépile 7 (second opérande) puis 14 (premier), on calcule 14 − 7 = 7, on empile : [7].

En notation habituelle : $(3+4)\times 2 - 7$.

Résultat : la pile ne contient plus que 7.

Chaque enfiler est un empiler sur entree : 50 opérations.

Le transfert déplace 50 éléments, chacun coûtant un depiler et un empiler : 50 + 50 = 100 opérations.

Les 50 defiler suivants sont de simples depiler sur sortie : 50 opérations, sans nouveau transfert puisque sortie n'est jamais vide avant la fin.

Total : 50 + 100 + 50 = 200 opérations.

Moyenne : 200 / 50 = 4 opérations par élément, quel que soit $n$.