Comment vérifier des parenthèses bien emboîtées avec une pile ?

Réponse courte

Parcours le texte de gauche à droite : empile chaque ouvrante ; pour une fermante, dépile une ouvrante disponible, sinon rejette. Le texte est bien équilibré si aucune erreur n’apparaît et si la pile est vide à la fin.

Comprendre

Pourquoi une pile convient

La dernière parenthèse ouvrante rencontrée doit être fermée avant les ouvrantes plus anciennes. C’est la règle LIFO d’une pile. On parcourt les caractères dans l’ordre et on conserve sur la pile les ouvrantes qui attendent encore une fermante.

Suivre l’algorithme

À la lecture d’une ouvrante, empile-la. À la lecture d’une fermante, vérifie d’abord que la pile n’est pas vide ; si elle l’est, rejette immédiatement. Sinon dépile une ouvrante. Les autres caractères, comme les lettres et les signes, sont ignorés ici. À la fin, accepte seulement si la pile est vide. Ainsi, « (a+(b)) » est équilibrée : la seconde ouvrante est fermée d’abord, puis la première. « ((a) » laisse une ouvrante en attente et doit être refusée.

Deux pièges

Une pile vide au début ne prouve pas que le texte est équilibré : « )x( » commence par une fermeture impossible. Vérifie cette erreur au moment de la lecture. La règle décrite porte sur les parenthèses rondes ; pour des crochets et accolades, il faut aussi mémoriser le type de chaque ouvrante afin de ne pas accepter « ([)] ».

Étapes

  1. Crée une pile vide et parcours les caractères du texte de gauche à droite.
  2. Quand tu lis « ( », ajoute cette ouvrante au sommet de la pile.
  3. Pour chaque fermante, rejette si la pile est vide ; sinon dépile une ouvrante.
  4. À la fin, accepte si et seulement si la pile est vide.

Exemples

  • (a+(b)) est accepté : les deux ouvrantes sont dépilées dans l’ordre inverse où elles ont été empilées.
  • Une fermeture au premier caractère est rejetée, car aucune ouvrante ne peut être retirée de la pile vide.

Pièges fréquents

  • Ne tester la pile qu’à la fin manque une fermeture prématurée comme dans « )(() » ; aucune opération de dépilement n’est possible au premier caractère.
  • Accepter dès que la pile redevient vide oublie qu’une ouvrante peut rester ensuite, comme dans « (a)( ».

Et maintenant ?

Questions proches

← Toutes les questions-réponses