Livre_silo 30 août 2013 16:32 Page 308
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
308
Informatique pour tous
On vérifie son résultat sur un exemple :
In [1]: parentheses('()(()())')
(0, 1)
(3, 4)
(5, 6)
(2, 7)
Out[1]: True
Exercice 12.2 * Supposons que l’on ne souhaite pas afficher les indices des parenthèses se correspondant, mais seulement renvoyer un booléen indiquant s’il s’agit d’un mot bien parenthésé. Simplifier le
programme précédent en conséquence. La structure de pile est-elle toujours nécessaire ?
Exercice 12.3 Adapter le programme 13 pour qu’il traite des mots constitués de plusieurs couples différents de symboles ouvrants et fermants, par exemple '(' et ')', mais aussi '[' et ']' ou '{' et '}'.
Un mot est alors bien parenthésé si le symbole fermant qui correspond à chaque symbole ouvrant est du
même type : le mot '{()}[]' est bien parenthésé mais '[(])' ne l’est pas.
Exercice 12.4 Adapter le programme 13 pour qu’il traite des mots constitués de parenthèses et d’autres
caractères, ces derniers n’interférant pas avec les parenthèses. Ainsi le mot '3+(4*(6-1)-2)' est bien
parenthésé, mais '(2+6)*3)' ne l’est pas.
Exercice 12.5 * Démontrer qu’un mot est bien parenthésé si et seulement s’il contient autant de parenthèses ouvrantes que de parenthèses fermantes et chacun de ses préfixes contient au moins autant
de parenthèses ouvrantes que de parenthèses fermantes. On pourra procéder par récurrence forte sur la
taille du mot.
Interpréter cette caractérisation en termes de comportement de la pile au cours de l’exécution de la
fonction parentheses.
Exercice 12.6 Écrire une fonction qui prend un entier n en argument et renvoie le mot ( n ) n , c’est-à-dire
le mot constitué de n parenthèses ouvrantes suivies de n parenthèses fermantes.
Exercice 12.7 Écrire une version récursive de la fonction parentheses. Que se passe-t-il quand on l’exécute sur le mot bien parenthésé imbriquant 1 000 paires de parenthèses (construit à l’aide de l’exercice
précédent) ? La fonction parentheses a-t-elle ce défaut ?
12.3.2 Évaluation d’une expression arithmétique en notation
polonaise inverse
Comme deuxième exemple, on souhaite réaliser un programme pour évaluer des expressions arithmétiques écrites en notation polonaise inverse (NPI), comme dans certaines
calculatrices. Dans cette notation, les opérateurs arithmétiques (+, ∗, etc.) sont placés
après leurs opérandes, en notation post-fixée. Ainsi, l’expression 2 + 3 s’écrit 2 3 + et l’expression 2 + 3 ∗ 4 devient 2 3 4 ∗ +. L’intérêt de cette notation est que les parenthèses
deviennent inutiles : par exemple, l’expression (2 + 3) ∗ 4 s’écrit simplement 2 3 + 4 ∗.
Par la suite, les expressions arithmétiques en NPI sont représentées par des tableaux
contenant des entiers et des caractères. Par exemple, 1 2 + 3∗ correspond au tableau
[1, 2, '+', 3, '*'].
L’ évaluation d’une expression en NPI nécessite une pile. L’idée consiste à parcourir le tableau de la gauche vers la droite et à empiler chaque nombre rencontré. Lorsque l’élément
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
308
Informatique pour tous
On vérifie son résultat sur un exemple :
In [1]: parentheses('()(()())')
(0, 1)
(3, 4)
(5, 6)
(2, 7)
Out[1]: True
Exercice 12.2 * Supposons que l’on ne souhaite pas afficher les indices des parenthèses se correspondant, mais seulement renvoyer un booléen indiquant s’il s’agit d’un mot bien parenthésé. Simplifier le
programme précédent en conséquence. La structure de pile est-elle toujours nécessaire ?
Exercice 12.3 Adapter le programme 13 pour qu’il traite des mots constitués de plusieurs couples différents de symboles ouvrants et fermants, par exemple '(' et ')', mais aussi '[' et ']' ou '{' et '}'.
Un mot est alors bien parenthésé si le symbole fermant qui correspond à chaque symbole ouvrant est du
même type : le mot '{()}[]' est bien parenthésé mais '[(])' ne l’est pas.
Exercice 12.4 Adapter le programme 13 pour qu’il traite des mots constitués de parenthèses et d’autres
caractères, ces derniers n’interférant pas avec les parenthèses. Ainsi le mot '3+(4*(6-1)-2)' est bien
parenthésé, mais '(2+6)*3)' ne l’est pas.
Exercice 12.5 * Démontrer qu’un mot est bien parenthésé si et seulement s’il contient autant de parenthèses ouvrantes que de parenthèses fermantes et chacun de ses préfixes contient au moins autant
de parenthèses ouvrantes que de parenthèses fermantes. On pourra procéder par récurrence forte sur la
taille du mot.
Interpréter cette caractérisation en termes de comportement de la pile au cours de l’exécution de la
fonction parentheses.
Exercice 12.6 Écrire une fonction qui prend un entier n en argument et renvoie le mot ( n ) n , c’est-à-dire
le mot constitué de n parenthèses ouvrantes suivies de n parenthèses fermantes.
Exercice 12.7 Écrire une version récursive de la fonction parentheses. Que se passe-t-il quand on l’exécute sur le mot bien parenthésé imbriquant 1 000 paires de parenthèses (construit à l’aide de l’exercice
précédent) ? La fonction parentheses a-t-elle ce défaut ?
12.3.2 Évaluation d’une expression arithmétique en notation
polonaise inverse
Comme deuxième exemple, on souhaite réaliser un programme pour évaluer des expressions arithmétiques écrites en notation polonaise inverse (NPI), comme dans certaines
calculatrices. Dans cette notation, les opérateurs arithmétiques (+, ∗, etc.) sont placés
après leurs opérandes, en notation post-fixée. Ainsi, l’expression 2 + 3 s’écrit 2 3 + et l’expression 2 + 3 ∗ 4 devient 2 3 4 ∗ +. L’intérêt de cette notation est que les parenthèses
deviennent inutiles : par exemple, l’expression (2 + 3) ∗ 4 s’écrit simplement 2 3 + 4 ∗.
Par la suite, les expressions arithmétiques en NPI sont représentées par des tableaux
contenant des entiers et des caractères. Par exemple, 1 2 + 3∗ correspond au tableau
[1, 2, '+', 3, '*'].
L’ évaluation d’une expression en NPI nécessite une pile. L’idée consiste à parcourir le tableau de la gauche vers la droite et à empiler chaque nombre rencontré. Lorsque l’élément