M1 MSI
I NITIATION ALGORITHMIQUE ET PROGRAMMATION
L ANGAGE PYTHON
T RAVAUX PRATIQUES
Brice Mayag
TP2 : P ILES ET F ILES
Exercice
1. Les piles définissent une structure de données de stockage qui suit une politique LIFO (Last In, First Out) d’ajout et
de retrait d’élément. Un moyen simple d’implanter la structure de données des piles est d’utiliser les listes python.
En supposant que les piles ont été implantées au moyen des listes python, écrire les fonctions usuelles d’ajout d’un
élément empiler(e,P), de retrait depiler(P), ainsi que la fonction sommet(P) qui rend le sommet de la
pile et la fonction estVide(P) qui teste si la pile est vide.
2. Les files définissent une structure de données de stockage qui suit une politique FIFO (First In, First Out) d’ajout et
de retrait d’élément. Un moyen simple d’implanter la structure de données des files est d’utiliser les listes python.
En supposant que les files ont été implantées au moyen des listes python, écrire les fonctions usuelles d’ajout et de
retrait ainsi que les deux fonctions qui respectivement rendent le premier élément de la file et testent si la file est
vide.
3. Écrire une fonction python qui permet de vérifier la validité des parenthèses, des accolades et des crochets contenus
dans une expression. Par exemple, cette fonction devra renvoyer Vrai pour l’expression suivante : (bonjour < a > est
ce que ca va )
4. On suppose manipuler des expressions arithmétiques sans variable définies à partir des 4 opérations arithmétiques
+; −; ×; ÷ et des entiers. La notation postfixée consiste à mettre les opérations arithmétiques après leurs 2
arguments. Ainsi, une expression arithmétique de la forme n • m où • ∈ {+; −; ×; ÷} a pour notation postfixée
l’expression nm•. On suppose que les expressions arithmétiques postfixées sont stockées dans une liste de chaînes
de caractères où chacune des chaînes de caractères représente soit un entier soit une opération arithmétique. Ecrire
une fonction qui à partir d’une expression arithmétique en notation postfixée, évalue cette expression et retourne le
résultat.
