Problème — Implémentation complète d'une pile par une classe

class Pile:
    """Type abstrait pile (LIFO) implemente par une liste."""

    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("depiler sur une pile vide")
        return self._contenu.pop()

    def sommet(self):
        if self.est_vide():
            raise IndexError("sommet sur une pile vide")
        return self._contenu[-1]

    def taille(self):
        return len(self._contenu)


def bien_ferme(expr):
    """Verifie l'appariement de (), [] et {}."""
    paires = {")": "(", "]": "[", "}": "{"}
    pile = Pile()
    for c in expr:
        if c in "([{":
            pile.empiler(c)             # ouvrante : on empile
        elif c in ")]}":
            if pile.est_vide():
                return False            # fermante sans ouvrante
            if pile.depiler() != paires[c]:
                return False            # mauvais appariement
    return pile.est_vide()             # tout doit etre referme

# Tests
print(bien_ferme("([]{})"))    # True
print(bien_ferme("([)]"))      # False (croisement)
print(bien_ferme("(()"))       # False (ouvrante en trop)

La pile mémorise les symboles ouvrants en attente. À chaque symbole fermant, on vérifie qu'il correspond au dernier ouvrant rencontré : c'est exactement le comportement LIFO. Toutes les opérations de pile étant en $O(1)$ et chaque caractère étant traité une fois, le coût total est $O(n)$.