Vérification du parenthésage — exercice corrigé de NSI (terminale) (chapitre 1)

Vérification du parenthésage

Structures de données linéaires · niveau 3 (difficile)

Énoncé

Vérification du parenthésage.

Écrire une fonction parentheses_correctes(expr) qui renvoie True si la chaîne expr est correctement parenthésée (chaque parenthèse ouvrante a une fermante correspondante, dans le bon ordre), et False sinon.

Corrigé

On utilise une pile : on empile chaque ( et, à chaque ), on dépile. Si l'on tente de dépiler une pile vide, ou s'il reste des parenthèses ouvrantes à la fin, l'expression est incorrecte.


def parentheses_correctes(expr):
    pile = []
    for caractere in expr:
        if caractere == "(":
            pile.append(caractere)      # parenthese ouvrante : on empile
        elif caractere == ")":
            if len(pile) == 0:
                return False            # une fermante sans ouvrante
            pile.pop()                  # on apparie avec une ouvrante
    return len(pile) == 0              # True si aucune ouvrante restante

# Tests
print(parentheses_correctes("(a+(b*c))"))   # True
print(parentheses_correctes("(a+b))"))      # False
print(parentheses_correctes("((a+b)"))      # False

La chaîne est parcourue une fois, chaque caractère provoquant au plus une opération de pile en $O (1)$ : le coût total est $O (n)$ .