Application pratique d'une pile : bon parenthésage

Dans les expressions arithmétiques ou dans les programmes informatiques, il est impératifs que les différents types de parenthèses s'ouvrent et se ferment correctement. On considérera ici trois type de parenthèses : les parenthèses usuelles (), les crochets [] et les accolades {}. Pour avoir un bon parenthésage, il y a deux règles à vérifier. La première, c'est qu'à chaque parenthèse ouvrante correspond une parenthèse fermante de même type. La seconde, c'est que les parenthèses ne se croisent pas.

Vous allez implémenter, grâce à une pile, une fonction qui vérifie qu'une chaine de caractère est bien parenthésée. On parle de parenthèse au sens large

Le principe est le suivant. Vous parcourez l'expression à vérifier. Pour chaque terme de l'expression :

• Si le caractère n'est pas une parenthèse, vous l'ignorez
• Si c'est une parenthèse ouvrante, vous l'empilez
• Si c'est une parenthèse fermante, vous comparez avec le sommet de la pile. Si le sommet de la pile est une parenthèse ouvrante de même type, on dépile. Sinon (soit la pile est vide, soit ce n'est pas la bonne parenthèse), l'expression est mal parenthésée.

À la fin du parcours, la pile doit être vide. Sinon, une parenthèse ouvrante n'a pas été refermée et la chaîne est mal parenthésée.

Notez que ce genre de fonctionnalité peut être utilisé dans les éditeurs de code que vous utilisez.