Comment détecter une parenthèse fermante mal placée avec une pile ?

Réponse courte

Au moment où tu lis une parenthèse fermante, regarde si une ouvrante attend sur la pile. Si elle est vide, la fermeture est mal placée : aucune suite du texte ne peut fournir une ouvrante avant elle.

Comprendre

Le test se fait tout de suite

Parcours le texte de gauche à droite et empile les parenthèses ouvrantes. Une parenthèse fermante doit correspondre à la dernière ouvrante encore en attente : si la pile est vide, il n’y en a aucune à fermer. Le texte est donc incorrect dès ce caractère, et tu peux arrêter le parcours.

Exemples de parcours

Dans « )( », le premier caractère est fermant et la pile est vide : rejet immédiat. Dans « (a)) », la première fermeture dépile l’ouvrante ; la seconde trouve alors une pile vide et révèle l’erreur. En revanche, dans « ((a) », aucune fermeture ne survient trop tôt ; l’erreur opposée est détectée après le parcours, car une ouvrante reste empilée.

Pièges propres à ce contrôle

Ne te contente pas de compter les ouvrantes et les fermantes : « )(() » en contient deux de chaque, mais commence par une fermeture impossible. Un nombre égal ne répare pas une erreur d’ordre. Ne dépile pas une valeur d’une pile vide : l’algorithme doit tester cette condition avant l’opération, ou il échoue au lieu de signaler proprement le texte invalide.

Étapes

  1. Initialise une pile vide et lis le texte de gauche à droite.
  2. Empile chaque parenthèse ouvrante rencontrée.
  3. Avant de dépiler pour une fermante, teste si la pile est vide et rejette si c’est le cas.
  4. Après le parcours, rejette aussi si une ouvrante reste dans la pile.

Exemples

  • Dans « (a)) », la première fermeture vide la pile ; la seconde est mal placée, car elle n’a plus d’ouvrante correspondante.
  • Le texte « )(() » possède deux ouvrantes et deux fermantes, mais son premier caractère suffit à le rejeter.

Pièges fréquents

  • Comparer seulement le nombre total de chaque type de parenthèse accepte à tort des fermetures placées avant toute ouverture.
  • Dépiler sans vérifier le vide transforme une entrée incorrecte en erreur de programme, au lieu de la détecter comme telle.

Et maintenant ?

Questions proches

← Toutes les questions-réponses