Livre_silo 30 août 2013 16:32 Page 306
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
306
Informatique pour tous
Dit autrement, l’ensemble des n opérations d’incrémentation de la taille n’a qu’un coût
total proportionnel à n, comme si chaque opération avait eu un coût constant (même si,
en réalité, certaines sont plus coûteuses que d’autres). On parle de complexité constante
amortie.
12.3 Applications
On va maintenant présenter plusieurs programmes utilisant une pile. Ces programmes
fonctionnent indifféremment avec l’une ou l’autre des réalisations présentées ci-avant.
12.3.1 Analyse des mots bien parenthésés
Comme première application des piles, on considère le problème suivant : étant donnée
une chaîne de caractères ne contenant que des caractères '(' et ')', déterminer s’il s’agit
d’un mot bien parenthésé. Un mot bien parenthésé est soit le mot vide, soit la concaténation
de deux mots bien parenthésés, soit un mot bien parenthésé mis entre parenthèses. Ainsi,
les trois mots '', '()()' et '(())()' sont bien parenthésés. À l’inverse, les mots '(()', '())'
ou encore ')(' ne le sont pas. On se propose de plus d’indiquer, pour chaque parenthèse
ouvrante, la position de la parenthèse fermante correspondante. Ainsi, pour le mot '(())()',
on donnera les couples d’indices (0, 3), (1, 2) et (4, 5).
L’idée consiste à parcourir le mot de la gauche vers la droite et à utiliser une pile pour
indiquer les indices de toutes les parenthèses ouvertes — et non encore fermées — vues
jusqu’à présent. On commence donc par créer une telle pile p :
def parentheses(s):
p = creer_pile(len(s))
La capacité maximale de la pile est ici la longueur du mot len(s) puisque, dans le pire des
cas, on aura un mot composé uniquement de parenthèses ouvrantes (on rappelle qu’avec
les piles non bornées, la capacité passée n’est pas significative). On parcourt alors tous les
caractères du mot, de la gauche vers la droite, avec une boucle for :
for i in range(len(s)):
Si le caractère est une parenthèse ouvrante, on empile son indice i :
if s[i] == '(':
empiler(p, i)
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
306
Informatique pour tous
Dit autrement, l’ensemble des n opérations d’incrémentation de la taille n’a qu’un coût
total proportionnel à n, comme si chaque opération avait eu un coût constant (même si,
en réalité, certaines sont plus coûteuses que d’autres). On parle de complexité constante
amortie.
12.3 Applications
On va maintenant présenter plusieurs programmes utilisant une pile. Ces programmes
fonctionnent indifféremment avec l’une ou l’autre des réalisations présentées ci-avant.
12.3.1 Analyse des mots bien parenthésés
Comme première application des piles, on considère le problème suivant : étant donnée
une chaîne de caractères ne contenant que des caractères '(' et ')', déterminer s’il s’agit
d’un mot bien parenthésé. Un mot bien parenthésé est soit le mot vide, soit la concaténation
de deux mots bien parenthésés, soit un mot bien parenthésé mis entre parenthèses. Ainsi,
les trois mots '', '()()' et '(())()' sont bien parenthésés. À l’inverse, les mots '(()', '())'
ou encore ')(' ne le sont pas. On se propose de plus d’indiquer, pour chaque parenthèse
ouvrante, la position de la parenthèse fermante correspondante. Ainsi, pour le mot '(())()',
on donnera les couples d’indices (0, 3), (1, 2) et (4, 5).
L’idée consiste à parcourir le mot de la gauche vers la droite et à utiliser une pile pour
indiquer les indices de toutes les parenthèses ouvertes — et non encore fermées — vues
jusqu’à présent. On commence donc par créer une telle pile p :
def parentheses(s):
p = creer_pile(len(s))
La capacité maximale de la pile est ici la longueur du mot len(s) puisque, dans le pire des
cas, on aura un mot composé uniquement de parenthèses ouvrantes (on rappelle qu’avec
les piles non bornées, la capacité passée n’est pas significative). On parcourt alors tous les
caractères du mot, de la gauche vers la droite, avec une boucle for :
for i in range(len(s)):
Si le caractère est une parenthèse ouvrante, on empile son indice i :
if s[i] == '(':
empiler(p, i)