Problème — Vérification du parenthésage avec une pile

L'idée est de parcourir l'expression : on empile chaque symbole ouvrant ; à chaque symbole fermant, on dépile et on vérifie la correspondance. À la fin, la pile doit être vide.

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

print(bien_parenthese("([]{})"))   # True
print(bien_parenthese("([)]"))     # False
print(bien_parenthese("(("))       # False

Pour "([)]", lorsqu'on rencontre ), le sommet est [ qui ne correspond pas : la fonction renvoie False. La complexité est en $O(n)$ où $n$ est la longueur de l'expression.