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

Application directe du cours · niveau 3 (difficile) · NSI (terminale), chapitre 9 — La programmation orientée objet

Énoncé

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

On souhaite vérifier qu'une expression contenant des parenthèses (), crochets [] et accolades \{\} est correctement parenthésée (chaque ouvrante est refermée par la bonne fermante, dans le bon ordre). Écrire une fonction bien_parenthese utilisant la classe Pile.

Corrigé

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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.