Terminale - Piles et Files

Exercices

Quelle structure de données choisir pour chacune des tâches suivantes ?

1. Stocker l'historique de des actions effectuées dans un logiciel et disposer d'une commande Annuler
2. Envoyer des fichiers à un serveur d'impression

Dans un logiciel de calcul formel, ou plus généralement dans un éditeur de texte permettant d'écrire des programmes, il y a une gestion dynamique du parenthésage. Par exemple, les expressions suivantes sont erronées : $$\left. \left( 4 + \sqrt{3} \right) \right) ^2 \hspace{2cm} \left( \left( 4 + x \right) \times 7 \right.$$ L'objectif de cet exercice est de proposer une solution informatique répondant à ce problème. On cherche ainsi à programmer une fonction recevant une chaîne de caractères constituée de parenthèses ouvrantes et fermantes, et retournant une liste de couples $(i,j)$ où $i$ est l'indice d'une parenthèses ouvrante, et $j$ l'indice de la parenthèse fermante correspondante. Si le parenthésage est incorrect, la fonction renvoie False.

>>> parenthesage("(4 + 3)*(2 + 1)")
[(0,6), (8,14)]
>>> parenthesage("2*(n + 3*(n+2))")
[(2,14), (9,13)]
>>> parenthesage("((4 + x)*7")
False

L'idée est de parcourir la chaîne de caractères et d'insérer dans une pile les indices des parenthèses ouvrantes rencontrées. Lorsque l'on rencontre une parenthèse fermante, on dépile alors l'indice de la parenthèse ouvrante correspondante.

Écrire la fonction parenthesage en utilisant la classe Pile définie précédemment.

La Notation Polonaise Inversée (NPI pour les intimes) permet d'écrire une succession d'opérations arithmétiques sans utiliser de parenthèses. Dans cette notation, les opérandes (les nombres) sont écrits avant les opérateurs (+,-,*,/).

Si OP désigne un opérateur et a et b deux opérandes, alors le calcul a OP b devient a b OP en NPI.

Par exemple, l'opération $4 + 3$ devient 4 3 +. De même, 6 - 4 devient 6 4 -.

En notation NPI, les opérandes précèdent l’opérateur et l'expression qui décrit chaque opérande disparaît lorsque l'opération est évaluée, pour être remplacée par la valeur calculée.

Par exemple, l'expression $3 \times (4 + 7)$ s'écrit 4 7 + 3 * en NPI. En effet, l'addition étant ici prioritaire sur la multiplication à cause des parenthèses, on indique d'abord 4 7 +, puis vient la multiplication 3 *.

La "lecture" de la NPI se fait de gauche à droite. Dès qu'un opérateur est rencontré, on effectue l'opération sur les deux nombres précédents.

1. Donner les NPI des opérations suivantes : $$ 2 \times 6 + 3 \hspace{1.5cm} 2 + 6 \times 3 \hspace{1.5cm} (2 + 6) \times 3 \hspace{1cm} (1 + 2) \times (3 - 4) \hspace{1cm} \frac{1 + 3 \times 4}{2 + 5} $$
Il n'y a pas unicité de la NPI ! Par exemple, $1 + 2 \times 3$ peut s'écrire 2 3 * 1 + ou 1 2 3 * +
Toutes les NPI n'ont pas forcément un sens, comme : 1 2 + * 5 4 +
2. Écrire une fonction calcul_NPI(liste) qui retourne le résultat d'un calcul écrit en NPI, sous la forme d'une liste d'opérandes et d'opérateurs.

>>> calcul_NPI([4, 7, "+", 3, "*"])
33
>>> calcul_NPI([1, 2, 3, "*", "+"])
7
>>> calcul_NPI([3, 11, "+", "*", 6])
False

L'idée est de parcourir la liste et d'empiler chaque nombre rencontré. Lorsqu'on rencontre un opérateur, on effectue l'opération sur les deux nombres les plus hauts de la pile. Si un opérateur est rencontré et qu'il y a moins de 2 nombres dans la pile, la NPI n'a pas de sens et la fonction retourne False.

L'algorithme Shunting-yard (littéralement, algorithme de la gare de triage) est une méthode d'analyse syntaxique d'une expression mathématique, et peut être utilisé pour traduire l'expression en notation polonaise inversée. Il a été inventé par Edsger Dijkstra (1930 - 2002), mathématicien et informaticien néerlandais, notamment connu pour l'algorithme éponyme, l'algorithme de Dijkstra, permettant de calculer des plus courts chemins dans un graphe orienté.

Dans sa forme simple, l'algorithme prend en entrée une liste d'opérandes, d'opérateurs et de parenthèses, et retourne la Notation Polonaise Inversée. La clé de l'algorithme est l'utilisation d'une pile stockant les opérateurs et les parenthèses ouvrantes.

Voici une description simplifiée de l'algorithme, ne prenant en compte que les opérateurs de base (+,-,*,/).

• Tant qu'il y a un élément dans la liste d'entrée :
• Lire l'élément
• Si c'est un nombre, l'ajouter à la liste de sortie
• Si c'est un opérateur OP1 :
• Tant qu'il y a un opérateur OP2 sur le haut de la pile, et que OP2 est de priorité supérieure à OP1:
• Dépiler OP2 et l'ajouter à la liste de sortie
• Empiler OP1
• Si c'est une parenthèse ouvrante, l'empiler
• Si c'est une parenthèse fermante, dépiler les opérateurs et les mettre dans la liste de sortie jusqu’à la première parenthèse ouvrante, qui elle aussi sera dépilée mais ne sera pas placée dans la liste de sortie
• Dépiler les opérateurs restants dans la liste de sortie

Transformation de 1 + 2 x 3 - 4 en 1 2 3 x 4 - +

1. Appliquer l'algorithme aux expressions suivantes : $$ 2 + 3 \times 6 \hspace{2cm} 2 \times (1 + 5) \hspace{2cm} 1 - 2 - 3 \hspace{2cm} (1 - 3) \times (2 + 6 \times 7) $$
2. Écrire une fonction conversion_NPI(L) qui retourne la notation polonaise inversée d'une expression donnée, passée sous forme de liste.

>>> conversion_NPI([1, '+', 2, '*', 3]) # 1 + 2 * 3
[1, 2, 3, '*', '+']
>>> conversion_NPI([6, '*', 7, '+', 1]) # 6 * 7 + 1
[6, 7, '*', 1, '+']
>>> conversion_NPI([20, '*', '(', 12, '+', 5, ')']) # 20 * (12 + 5)
[20, 12, 5, '+', '*']

Grâce à ce qui a été fait dans les exercices précédents, nous sommes à même de calculer n'importe quelle expression arithmétique donnée sous forme de liste. Il ne nous reste plus qu'à transformer une expression donnée sous forme de chaîne de caractères en liste, afin de créer un mini-calculatrice gérant les ordres de priorité et le parenthésage.

1. Écrire une fonction conversion_liste(expression) qui retourne une expression arithmétique en une liste composée des différents opérateurs, opérandes et parenthèses de cette expression.

   >>> conversion_liste("1+2")
   [1, '+', 2]
   >>> conversion_liste("2 *(1 +4)")
   [2, '*', '(', 1, '+', 4, ')']
   >>> conversion_liste("26 + 3 * (177 - 8)")
   [26, '+', 3, '*', '(', 177, '-', 8, ')']

   Pour simplifier le problème, on pourra se contenter d'expressions sans espaces et ne faisant intervenir que des chiffres, et non des nombres de plus de 2 chiffres.
2. En utilisant toutes les fonctions codées dans ce cours, écrire une fonction calculatrice(expression) qui retourne le résultat d'une expression donnée.

   >>> calculatrice("1 + 2")
   3
   >>> calculatrice("1 + 2 * (3 + 5)")
   17