Pour chaque question, une seule réponse est correcte.
1. On empile successivement les lettres A, B, C, D dans une pile initialement vide. On dépile ensuite deux fois. Quelle est la lettre au sommet de la pile ?
Correction publiée après la séance.
2. On enfile les lettres A, B, C dans une file, puis on défile une fois. Quelle lettre est renvoyée ?
Correction publiée après la séance.
3. Parmi les situations suivantes, laquelle correspond à une pile ?
Correction publiée après la séance.
4. Quelle opération est interdite sur une pile ?
Correction publiée après la séance.
5. On implémente une pile à l’aide du type list de Python en utilisant append pour empiler et pop() pour dépiler. Quelle est la complexité de ces deux opérations ?
append en \(O(n)\), pop() en \(O(n)\)append en \(O(1)\), pop() en \(O(1)\)append en \(O(1)\), pop() en \(O(n)\)append en \(O(n)\), pop() en \(O(1)\)Correction publiée après la séance.
On considère une pile p initialement vide. On exécute les instructions suivantes :
p.empiler(4)
p.empiler(7)
p.empiler(2)
a = p.depiler()
p.empiler(9)
b = p.depiler()
p.empiler(1)
c = p.depiler()
a, b et c :| Instruction | État de la pile (bas → haut) | Variable |
|---|---|---|
empiler(4) |
||
empiler(7) |
||
empiler(2) |
||
depiler() |
a = |
|
empiler(9) |
||
depiler() |
b = |
|
empiler(1) |
||
depiler() |
c = |
empiler pose l’élément au sommet, c’est-à-dire à droite de l’état écrit du bas vers le haut. depiler retire l’élément du sommet et le renvoie : c’est lui qui va dans la variable.
Après ces instructions, quels éléments restent dans la pile ? Dans quel ordre ?
Lire la dernière ligne du tableau : ce sont les éléments restants, du bas vers le sommet.
Correction publiée après la séance.
Pile à trousCompléter les méthodes de la classe Pile implémentée avec le type list de Python.
Pile à trous (suite)class Pile:
def __init__(self):
self.contenu = ... # créer une liste vide
def est_vide(self):
return ... # vrai si la liste est vide
def empiler(self, element):
... # ajouter en fin de liste
def depiler(self):
if self.est_vide():
raise ValueError("pile vide")
return ... # retirer et renvoyer le dernier élément
def sommet(self):
"""Renvoie l'élément au sommet sans le retirer."""
if self.est_vide():
raise ValueError("pile vide")
return ... # accéder au dernier élément
def __len__(self):
return ... # nombre d'éléments
Toutes les opérations portent sur la liste self.contenu : append ajoute en fin, pop() retire et renvoie le dernier élément, self.contenu[-1] est le dernier élément et len(self.contenu) le nombre d’éléments. La pile est vide quand cette longueur vaut 0.
Pile à trous (suite)Correction publiée après la séance.
En s’inspirant de l’exercice précédent, écrire une classe File implémentée avec le type list de Python.
La classe doit comporter les méthodes suivantes :
est_vide(self) : renvoie True si la file est vide ;enfiler(self, element) : ajoute un élément en fin de file ;defiler(self) : retire et renvoie l’élément en début de file ;__len__(self) : renvoie le nombre d’éléments.Indication : pour retirer le premier élément d’une liste, on utilise pop(0).
Tester avec :
f = File()
f.enfiler("Alice")
f.enfiler("Bob")
f.enfiler("Charlie")
print(f.defiler()) # doit afficher Alice
print(f.defiler()) # doit afficher Bob
Même structure que la classe Pile : une liste self.contenu, dont les éléments s’ajoutent en fin avec append. Seule différence, defiler retire le premier élément, avec pop(0).
class File:
def __init__(self):
self.contenu = []
def est_vide(self):
return len(self.contenu) == ...
def enfiler(self, element):
self.contenu.append(...)
def defiler(self):
return self.contenu.pop(...)
def __len__(self):
return ...
Correction publiée après la séance.
La notation polonaise inversée (NPI) est une façon d’écrire les calculs sans parenthèses. On écrit d’abord les opérandes, puis l’opérateur. Par exemple :
3 4 + ;3 4 + 2 * ;3 4 2 * +.L’évaluation utilise une pile selon l’algorithme suivant :
5 3 + 8 2 - * en complétant le tableau :| Jeton lu | Action | État de la pile (bas → haut) |
|---|---|---|
5 |
empiler 5 | 5 |
3 |
||
+ |
||
8 |
||
2 |
||
- |
||
* |
Pour un opérateur, le premier nombre dépilé est l’opérande de droite et le second celui de gauche : pour 8 2 -, on calcule 8 − 2. Le résultat est empilé à la place des deux opérandes.
Écrire une fonction evaluer_npi(expression) qui prend en paramètre une chaîne de caractères (jetons séparés par des espaces) et renvoie le résultat du calcul en utilisant la classe Pile.
expression.split() donne la liste des jetons. Pour chaque jeton : si c’est un opérateur, dépiler deux nombres, calculer, puis empiler le résultat ; sinon, empiler float(jeton). À la fin, le résultat est le seul élément de la pile.
def evaluer_npi(expression):
p = Pile()
for jeton in expression.split():
if jeton in "+-*/":
droite = p.depiler()
gauche = p.depiler()
if jeton == "+":
p.empiler(gauche + droite)
elif jeton == "-":
p.empiler(...)
elif jeton == "*":
p.empiler(...)
else:
p.empiler(...)
else:
p.empiler(float(jeton))
return ...
Tester avec evaluer_npi("5 3 + 8 2 - *") qui doit renvoyer 48.
Correction publiée après la séance.
Un problème classique en compilation est de vérifier si les parenthèses et crochets d’une expression sont correctement appariés. Par exemple :
"(a + [b * c])" est valide ;"(a + [b * c)]" est invalide (croisement des délimiteurs) ;"(a + b" est invalide (parenthèse non fermée).Algorithme : on parcourt les caractères un par un. Si on rencontre un ouvrant (( ou [), on l’empile. Si on rencontre un fermant () ou ]), on vérifie que le sommet de la pile correspond à l’ouvrant attendu. À la fin, la pile doit être vide.
Dérouler l’algorithme sur "[a + (b * c)]" en montrant l’état de la pile après chaque ouvrant ou fermant.
Seuls les caractères [, (, ) et ] comptent : un ouvrant est empilé ; un fermant dépile le sommet, qui doit être l’ouvrant du même type.
Écrire une fonction parenthesage_valide(expression) qui renvoie True si le parenthésage est correct, False sinon.
Parcourir les caractères. Un ouvrant est empilé. Pour un fermant, renvoyer False si la pile est vide ou si l’ouvrant dépilé ne lui correspond pas. Après la boucle, le parenthésage n’est correct que si la pile est vide.
def parenthesage_valide(expression):
p = Pile()
for c in expression:
if c in "([":
p.empiler(c)
elif c in ")]":
if p.est_vide():
return False
ouvrant = p.depiler()
if (c == ")" and ouvrant != "(") or (c == "]" and ouvrant != ...):
return ...
return p.est_vide()
Tester sur les exemples suivants :
"()" → True"([a + b] * (c - d))" → True"(a + b]" → False"((" → FalseCorrection publiée après la séance.
On souhaite inverser l’ordre des éléments d’une file sans utiliser de tableau ni de liste auxiliaire, mais uniquement une pile.
Expliquer en quelques phrases le principe de la méthode.
Une pile rend les éléments dans l’ordre inverse de celui où ils ont été empilés : que se passe-t-il si l’on défile tous les éléments de la file pour les empiler, puis qu’on les dépile pour les enfiler de nouveau ?
Écrire une fonction inverser_file(f) qui prend une file f en paramètre et inverse ses éléments sur place.
Deux boucles while se suivent : la première vide la file dans la pile, la seconde vide la pile dans la file.
def inverser_file(f):
p = Pile()
while not f.est_vide():
p.empiler(f.defiler())
while not p.est_vide():
f.enfiler(...)
Tester : si la file contient initialement A ← B ← C (A en tête), après inversion elle doit contenir C ← B ← A (C en tête).
Enfiler A, B et C, appeler inverser_file, puis défiler les éléments un par un en les affichant.
Correction publiée après la séance.
On modélise une file d’attente d’imprimante. Chaque document est représenté par un dictionnaire {"nom": ..., "pages": ...}.
Créer une classe FileImpression avec les méthodes :
soumettre(self, nom, pages) : ajoute un document à la file ;imprimer_suivant(self) : retire le prochain document de la file, affiche "Impression de [nom] (X pages)" et renvoie le nombre de pages ;documents_en_attente(self) : renvoie le nombre de documents restants ;pages_restantes(self) : renvoie le nombre total de pages en attente.Ranger les documents dans une liste de dictionnaires {"nom": ..., "pages": ...}. imprimer_suivant retire le premier avec pop(0), comme dans la classe File, et pages_restantes additionne les pages de tous les documents de la liste.
class FileImpression:
def __init__(self):
self.documents = []
def soumettre(self, nom, pages):
self.documents.append({"nom": nom, "pages": pages})
def imprimer_suivant(self):
doc = self.documents.pop(...)
print(f"Impression de {doc['nom']} ({doc['pages']} pages)")
return ...
def documents_en_attente(self):
return ...
def pages_restantes(self):
total = 0
for doc in self.documents:
total = ...
return total
Simuler le scénario suivant :
Traduire chaque ligne du scénario par un appel de méthode : soumettre pour un dépôt, imprimer_suivant pour une impression.
Afficher le nombre total de pages imprimées.
Additionner les valeurs renvoyées par les appels à imprimer_suivant.
Correction publiée après la séance.