Livre_silo 30 août 2013 16:32 Page 307
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
307
12 – Structure de pile
Sinon, c’est qu’il s’agit d’une parenthèse fermante ². Si la pile est vide, c’est que le mot
n’ est pas bien parenthésé, car on vient de trouver une parenthèse fermante à laquelle ne
correspond aucune parenthèse ouvrante. On le signale en renvoyant immédiatement False :
else:
if est_vide(p):
return False
Sinon, on dépile l’indice j de la dernière parenthèse ouvrante rencontrée et on affiche le
couple (j,i) pour signifier que la parenthèse ouvrante à l’indice j correspond à la parenthèse
fermante à l’indice i :
j = depiler(p)
print((j, i))
On voit ici en quoi le choix de la structure de pile est pertinent : il permet de faire correspondre chaque parenthèse fermante à la parenthèse ouvrante la plus proche, c’est-à-dire
la dernière qui avait été rencontrée. Quand enfin on sort de la boucle for, il ne reste plus
qu’à vérifier que la pile est bien vide :
return est_vide(p)
En effet, le mot pourrait contenir plus de parenthèses ouvrantes que de parenthèses fermantes, comme '((', et il faut alors signaler que le mot n’est pas bien parenthésé.
Le code complet est donné ci-après.
PROGRAMME 13 Mots bien parenthésés
def parentheses(s):
p = creer_pile(len(s))
for i in range(len(s)):
if s[i] == '(':
empiler(p, i)
else:
if est_vide(p):
return False
j = depiler(p)
print((j, i))
return est_vide(p)
2. On a supposé ici que le mot ne contenait que des parenthèses. Le programme pourrait être plus défensif
et se prémunir contre l’éventuelle occurrence d’autres caractères.