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
- Initialise une pile vide et lis le texte de gauche à droite.
- Empile chaque parenthèse ouvrante rencontrée.
- Avant de dépiler pour une fermante, teste si la pile est vide et rejette si c’est le cas.
- 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.
