TP5 : piles (LIFO)

Description théorique

Une pile (ou stack, ou encore LIFO, pour Last In, First Out) est une structure de données très courante. Quasiment tous les ordinateurs utilisent au moins une pile pour fonctionner, la fameuse pile d’appels. C’est par le biais de cette pile d’appels que sont transmis les paramètres des fonctions, leurs valeurs de retour, l’allocation des variables locales, et bien d’autres choses.

Le fonctionnement d’une pile est assez simple à comprendre : il suffit d’imaginer une pile d’assiettes très fragiles et savonneuses. On peut ajouter une assiette en haut de la pile, et enlever l’assiette qui est en haut de la pile ; mais on ne peut pas ajouter ou enlever une assiette en plein milieu, sous peine de faire tomber toutes les assiettes !

Les deux opérations de base sont appelées push et pop et correspondent respectivement à « ajouter une assiette » en haut de la pile, et « enlever l’assiette qui est en haut de la pile ». Si on remplace « assiette » par « donnée », on y est.

On emploie une pile lorsqu’on utilise une calculatrice en Notation Polonaise Inversée (RPN pour les intimes) ; par exemple, l’opération 10×5+4×2 devient, en RPN : « 10 5 × 4 2 x + ». Traduction :

1. Ajouter le nombre 10 en haut de la pile.
2. Ajouter le nombre 5 en haut de la pile.
3. Retirer les deux nombres qui sont en haut de la pile, les multiplier, et mettre le résultat en haut de la pile.
4. Ajouter le nombre 4 en haut de la pile.
5. Ajouter le nombre 2 en haut de la pile.
6. Retirer les deux nombres qui sont en haut de la pile, les multiplier, et mettre le résultat en haut de la pile.
7. Retirer les deux nombres qui sont en haut de la pile, les additionner, et mettre le résultat en haut de la pile. 

Définition (simpliste) d’une pile en Python

On va utiliser une classe stack, à l’intérieur de laquelle on stockera le contenu de la pile sous forme d’un tableau. Le « fond » de la pile sera le premier élément du tableau, le « sommet » de la pile sera le dernier élément du tableau.

Le seul travail du constructeur sera d’initialiser ce tableau.

Écrire cette classe stack (il n’y a presque rien à faire).

Opérations de base : push et pop

Implémenter ensuite deux méthodes dans notre classe stack : la fonction push, qui prend comme paramètre l’élément à ajouter au sommet de la pile (c’est-à-dire à ajouter à la fin du tableau), et la fonction pop qui retire l’élément au somme de la pile et le retourne.

Opérations arithmétiques

Implémenter ensuite quatre méthodes, appelées op_add, op_sub, op_mul, op_div ; ces fonctions ne prennent aucun argument. Elles doivent dépiler (c’est-à-dire retirer, en faisant appel à la fonction pop) les deux éléments au sommet de la pile, effectuer l’opération correspondante, et empiler avec push le résultat.

Exemple :

s = stack()
s.push(4)
s.push(10)
s.op_add()
resultat = s.pop()
# resultat doit contenir 14

Implémentation d’un parser RPN

On veut pouvoir calculer une expression polonaise inversée comme celle décrite dans l’introduction.

La première tâche sera de transformer une chaîne de caractères en suite de tokens. Un token, dans ce cas précis, cela peut être ou bien un nombre, ou bien une des opération : « + – * / ».

Écrire une fonction tokenize (en dehors de la classe stack), qui prend en argument une chaîne de caractères et retourne une liste de tokens. Par exemple :

tokens = tokenize("10 5 * 4 2 * +")
# tokens doit être la liste [10, 5, "*", 4, 2, "*", "+"]

Si jamais la chaîne contient un token invalide (c’est-à-dire quelquechose qui n’est ni un nombre, ni une des quatre opérations autorisées), il faut lever une exception ; par exemple en faisant raise Exception(“Invalid Token : …”) et en mettant le token qui a posé problème dans le message de l’exception.

Tester la fonction tokenize avec diverses chaînes (correctes et incorrectes).

Évaluation d’une liste de tokens

Écrire ensuite une fonction eval dans la classe stack, qui prend pour argument une liste de tokens ; les tokens qui sont des nombres devront être empilés avec la méthode push, et les tokens qui sont des opérations devront être évalués (en appelant les fonctions op_… correspondantes).

La suite …

Dans la suite, nous verrons comment construire un arbre d’évaluation à partir d’une suite de tokens ; pour cela, nous utiliserons une classe stack2tree qui héritera de la classe stack et une classe tree inspirée de celle du TP4, où chaque noeud sera ou bien un nombre, ou bien un opérateur (c’est-à-dire un noeud avec un opérateur, un fils gauche, et un fils droit).