Vérification du parenthésage

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)$.