Chapitre : Piles & Files
1-Les piles : Une pile est une structure de données de type LIFO (last in first out) : le dernier entré
est le premier sorti. Une pile P est entièrement définie par deux opérations
1. empiler une valeur : c’est l’insérer au début de P,
2. dépiler une valeur, si P est non vide, c’est sélectionner la première valeur de la pile et la
supprimer de P
Représentation D'une Pile Par Liste
""" Tester si une pile est vide """ Le sommet de la pile """
""" def sommet(pile):
def vide(pile): if(not vide(pile)):return
return len(pile) == 0 pile[0]
return 'La pile est vide !!'
""" Empiler un élément x """ Dépiler une pile """
dans la pile """ def depiler(pile):
def empiler(x,pile): if(not vide(pile)):
return [x] + pile x = sommet(pile)
del(pile[0])
return x
return 'La pile est vide !!'
2-Les Files : Une file est une structure de
données de type FIFO (first in first out) : le
premier entré est le premier sorti.
Une file F est entièrement définie par deux
opérations :
1. enfiler une valeur : c’est l’ajouter à la fin
de de F,
2. défiler une valeur : c’est sortir une valeur, si F est non vide, c’est sélectionner la première valeur
de F et la supprimer de F
La première valeur de la file F est la tête de la file et la dernière est la queue de la file
Représentation d'une pile par liste
""" Tester si une file est vide """ """ Enfiler un élément x dans une file """
def vide (File): def enfiler(x,file):
return (len(File)==0) return file + [x]
""" Défiler une file et renvoie l'élément défilé """
def defiler(file):
if(not vide(file)):
x = file[0]
del (file[0])
return x
return 'La file est vide !!'
1
TP :
Parenthésage
Le but de cet exercice est d’écrire un programme en Python capable de vérifier si une expression
est bien parenthésée ou pas. Les trois types de parenthésage qui seront pris en compte sont les
parenthèses (, ), les crochets [, ] et les accolades {, }.
Votre programme doit par exemple retourner True pour les expressions suivantes :
[a+(b+c)]
[((5*3)+(2*10))/2]
et False pour
[a+(b+c)
[a+(b+c(]
La façon la plus simple de réaliser un tel programme c’est à l’aide d’une pile. Au départ la pile est
vide. Ensuite, on lit l’expression, caractère par caractère :
Si le caractère lu est un symbole ouvrant, alors on empile le caractère fermant correspondant.
Si le caractère lu est identique au sommet de la pile, on dépile ce caractère.
Nous pouvons constater que lorsque le parenthésage est correct, la pile sera vide après que tous
les caractères sont lus.
Dans l’exemple suivant vous pouvez observer l’évolution de la pile à chaque lecture d’un nouveau
caractère de l’expression [a+(b+c)].
Voici une fonctionnalité des listes en Python qui peut vous aider dans la réalisation de votre
programme :
>>> L = ['a', 'b', 'c', 'd']
>>> L.pop()
'd'
>>> print(L)
['a', 'b', 'c']
La méthode pop()appliquée à une liste, dépile et renvoie l’élément au sommet de la pile. La
méthode append(a)quant à elle, ajoute l’élément a au sommet de la pile.
>>> L.append('e')
>>> print(L)
['a', 'b', 'c', 'e']
Pour réaliser votre programme vous pouvez suivre ces étapes :
Écrire une fonction estOuvrante(c) qui prend en entrée un caractère c et qui renvoie True si c est
un symbole ouvrant.
Écrire une fonction fermante(c) qui prend en entrée un caractère c. Si ce caractère est un symbole
ouvrant, alors la fonction doit renvoyer le symbole fermant correspondant. Dans le cas contraire
elle doit renvoyer None.
Écrire et tester la fonction qui vérifie le parenthèsage.
2
Notation polonaise inverse
La notation polonaise inverse (NPI), ou notation post-fixée, est une marnière d’écrire les
expressions mathématiques en se passant des parenthèses. Elle a été introduite par le
mathématicien polonais Jan Lucasievicz dans les années 1920.
Le principe de cette méthode est de placer chaque opérateur juste après ses deux opérandes.
L’expression 2+3 devient en NPI 2 3 +.
Regardons maintenant comment peuvent s’écrire les opérations un peu plus complexes au moyen
de cette notation
2+6−1 s’écrit 2 6 + 1 -
5*3+4 s’écrit 5 3 * 4 +
((1+2)*4)+3 s’écrit 1 2 + 4 * 3 +
Évaluer une expression post-fixée est facile. Pour cela il suffit de lire l’expression de gauche à droite
et d’appliquer chaque opérateur aux deux opérandes qui le précèdent. Si l’opérateur n’est pas le
dernier symbole on replace le résultat intermédiaire dans l’expression et on recommence avec
l’opérateur suivant.
Le but de l’exercice est de réaliser en Python une calculatrice simple, capable d’évaluer une
formule en NPI et de retourner le résultat arithmétique. La réalisation d’une telle calculatrice se
ferra à l’aide d’une pile.
L’algorithme est très simple. On commence par lire un par un les caractères de l’expression. Si le
caractère lu est un opérande alors on l’empile. Si le caractère lu est un opérateur, alors on dépile
les deux éléments se trouvant en haut de la pile, on calcule le résultat en appliquant l’opérateur sur
les deux opérandes dépilées et on empile le résultat. Une fois tous les caractères lus, la pile ne
contient qu’un seul élément qui correspond au résultat final.
Voyons avec un exemple l’état de la pile après la lecture de chaque caractère de
l’expression ((1+2)∗4)+3, ou 1 2 + 4 * 3 + en NPI.
Vous pouvez remarquer que le résultat final 15 se trouve au sommet de la pile après la fin du
programme.
Écrivez maintenant un programme Python qui met en oeuvre tout cela. Les caractères autorisés
sont les chiffres de 0 à 9, ainsi que les symboles +,−,*,/ correspondant aux 4 opérations
élémentaires.
Votre programme pourrait se composer des fonctions suivantes :
Une fonction estOperateur(c) qui prend en entrée un caractère et renvoie True s’il s’agit d’un
opérateur et False sinon.
Une fonction calcul(op, n, m) qui prend en entrée un opérateur op parmi les quatre opérateurs
autorisés et deux entiers n et m et qui renvoie le résultat du calcul n op m.
La fonction evaluation(s) qui prend en entrée une expression sous-forme de chaîne de caractères
en notation polonaise inverse et renvoie le résultat du calcul.
Testez votre programme pour le calcul de l’expression 5*(8−3)*3+((3−1)*2)/3 dont l’écriture en NPI
est 5 8 3 − * 3 * 3 1 − 2 * 3 / +.
3
