%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]] %% nav-fin %% # Piles et Files ## 🎯 Objectif Mettre en œuvre une **pile** et une **file** pour résoudre deux problèmes classiques : l'**évaluation d'une expression** et la **génération ordonnée** d'une suite de nombres. ## 📄 Énoncé Dans cet atelier, on s’intéresse à deux situations algorithmiques classiques : 1. **L’évaluation d’expressions en notation polonaise inverse (NPI)**, qui repose sur l’utilisation d’une **pile**. 2. **La génération de la suite de Hamming**, qui s’appuie sur des **files** pour explorer efficacement un espace de solutions. L’objectif est de comprendre comment une pile et une file fixent l’ordre de traitement des données. ## 🔎 Observer avant de programmer **Partie 1 :** une expression en notation polonaise inverse se lit de gauche à droite. Un nombre est empilé. Un opérateur dépile deux nombres et empile le résultat. ```sq-npi expression: 5 8 3 - * 3 * 3 1 - 2 * 3 / + ``` **Partie 2 :** les nombres de Hamming n’ont pas d’autre facteur premier que 2, 3 et 5. Trois files produisent ces nombres dans l’ordre croissant. ```sq-hamming n: 12 ``` ## 🧩 Travail demandé ### Partie 1 – Pile et notation polonaise inverse 1. Lire la classe `Pile` et les fonctions `est_operateur` et `calcul`, puis exécuter la cellule de préparation. 2. Écrire `calcul_npi(s, trace=True)`, qui évalue une expression en notation polonaise inverse et renvoie le résultat. 3. Avec `trace=True`, afficher la pile après chaque jeton lu. ### Partie 2 – File et suite de Hamming 1. Lire la classe `File`, puis exécuter la cellule de préparation. 2. Écrire `hamming(n)`, qui renvoie le n-ième nombre de Hamming. 3. Afficher les 30 premiers nombres de Hamming. ## 💻 Programmer dans la page Les cellules s'exécutent dans le navigateur. Elles partagent les mêmes variables : exécutez-les dans l'ordre. Le premier lancement charge Python en quelques secondes. ### Partie 1 – La notation polonaise inverse La notation polonaise inverse (NPI), ou notation postfixée, écrit chaque opérateur après ses deux opérandes. Elle n'a pas besoin de parenthèses. | Expression usuelle | Notation polonaise inverse | |---|---| | 2 + 3 | `2 3 +` | | 2 + 6 − 1 | `2 6 + 1 -` | | 5 × 3 + 4 | `5 3 * 4 +` | | ((1 + 2) × 4) + 3 | `1 2 + 4 * 3 +` | L'évaluation utilise une pile. On lit les jetons de gauche à droite : - un nombre est empilé ; - un opérateur dépile `b`, puis `a`, calcule `a op b` et empile le résultat. À la fin, la pile contient un seul élément : le résultat. L'ordre de dépilement compte pour `-` et `/`. **Préparation :** la classe `Pile` est celle de la page [[Code et Développement/Programmation/Piles et Files/01_Les piles|Les piles]]. ```sq-python class Pile: def __init__(self): self.elements = [] def empile(self, element): self.elements.append(element) def depile(self): if self.elements: return self.elements.pop() def taille(self): return len(self.elements) def sommet(self): if len(self.elements) == 0: raise Exception("La pile est vide") return self.elements[-1] def __str__(self): if not self.elements: return "Pile vide" return "Pile : " + " -> ".join(str(x) for x in reversed(self.elements)) def est_operateur(x): """Renvoie True si x est l'un des quatre opérateurs.""" return x in ["+", "-", "*", "/"] def calcul(op, a, b): """Renvoie a op b.""" if op == "+": return a + b elif op == "-": return a - b elif op == "*": return a * b else: return a / b print(calcul("-", 8, 3)) #--- sortie 5 ``` **Question 1 :** écrivez `calcul_npi(s, trace=True)`. La chaîne `s` contient des jetons séparés par des espaces : `s.split()` les donne dans l'ordre. ```sq-python def calcul_npi(s, trace=True): p = Pile() # À compléter : parcourir s.split(), empiler les nombres, appliquer les opérateurs # Si trace vaut True, afficher p après chaque jeton return p.depile() print(calcul_npi("5 8 3 - * 3 * 3 1 - 2 * 3 / +")) #--- correction def calcul_npi(s, trace=True): p = Pile() for jeton in s.split(): if est_operateur(jeton): b = p.depile() a = p.depile() p.empile(calcul(jeton, a, b)) else: p.empile(int(jeton)) if trace: print(p) return p.depile() print(calcul_npi("5 8 3 - * 3 * 3 1 - 2 * 3 / +")) #--- tests assert calcul_npi("2 3 +", trace=False) == 5, "2 3 + doit valoir 5" assert calcul_npi("2 6 + 1 -", trace=False) == 7, "2 6 + 1 - doit valoir 7 : attention à l'ordre de dépilement" assert calcul_npi("5 3 * 4 +", trace=False) == 19, "5 3 * 4 + doit valoir 19" assert calcul_npi("1 2 + 4 * 3 +", trace=False) == 15, "1 2 + 4 * 3 + doit valoir 15" assert calcul_npi("8 2 /", trace=False) == 4, "8 2 / doit valoir 4 : a / b, et non b / a" assert abs(calcul_npi("5 8 3 - * 3 * 3 1 - 2 * 3 / +", trace=False) - 76.33333333333333) < 1e-9, "l'expression de l'énoncé vaut 76.333…" ``` ### Partie 2 – La suite de Hamming Un nombre de Hamming est un entier naturel non nul dont les seuls facteurs premiers sont 2, 3 et 5. Les 30 premiers sont : 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80. La méthode par force brute teste chaque entier un par un. Elle devient lente, car les nombres de Hamming se raréfient. Tout nombre de Hamming autre que 1 est le produit par 2, 3 ou 5 d'un nombre de Hamming plus petit. On utilise donc trois files `f2`, `f3` et `f5`, qui contiennent au départ le seul entier 1. À chaque étape : 1. on note `m` le plus petit des trois nombres en tête de file : c'est le nombre de Hamming suivant ; 2. on défile `m` de chaque file qui l'a en tête ; 3. on enfile `2 × m` dans `f2`, `3 × m` dans `f3` et `5 × m` dans `f5`. **Préparation :** la classe `File` est celle de la page [[Code et Développement/Programmation/Piles et Files/02_Les files|Les files]]. ```sq-python class File: def __init__(self): self.elements = [] def enfile(self, element): self.elements.append(element) def defile(self): if self.elements: return self.elements.pop(0) def taille(self): return len(self.elements) def tete(self): if len(self.elements) == 0: raise Exception("La file est vide") return self.elements[0] def __str__(self): if not self.elements: return "File vide" return "File : " + " <- ".join(str(x) for x in self.elements) f = File() f.enfile(1) f.enfile(2) print(f) #--- sortie File : 1 <- 2 ``` **Question 2 :** écrivez `hamming(n)`, qui renvoie le n-ième nombre de Hamming. `hamming(1)` vaut 1. ```sq-python def hamming(n): f2 = File() f3 = File() f5 = File() f2.enfile(1) f3.enfile(1) f5.enfile(1) # À compléter : répéter n fois les trois étapes de la méthode return None print([hamming(i) for i in range(1, 31)]) #--- correction def hamming(n): """Renvoie le n-ième nombre de Hamming : hamming(1) vaut 1.""" f2 = File() f3 = File() f5 = File() f2.enfile(1) f3.enfile(1) f5.enfile(1) for i in range(n): m = min(f2.tete(), f3.tete(), f5.tete()) if m == f2.tete(): f2.defile() if m == f3.tete(): f3.defile() if m == f5.tete(): f5.defile() f2.enfile(2 * m) f3.enfile(3 * m) f5.enfile(5 * m) return m print([hamming(i) for i in range(1, 31)]) #--- tests assert hamming(1) == 1, "hamming(1) doit valoir 1" assert hamming(12) == 16, "hamming(12) doit valoir 16" assert [hamming(i) for i in range(1, 31)] == [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80], "les 30 premiers nombres ne correspondent pas" assert hamming(2002) == 8153726976, "hamming(2002) doit valoir 8153726976" ``` Cette méthode est bien plus rapide que la force brute. Elle n'est pas optimale : un même nombre peut se trouver dans deux ou trois files, par exemple 6 dans `f2` et dans `f3`. **Question 3 (pour aller plus loin) :** écrivez `hamming2(n)`, qui donne les mêmes valeurs sans jamais enfiler deux fois le même nombre. Règle : si `m` vient de `f2`, on enfile `2m`, `3m` et `5m` ; s'il vient de `f3`, on enfile `3m` et `5m` ; s'il vient de `f5`, on enfile seulement `5m`. ```sq-python def hamming2(n): f2 = File() f3 = File() f5 = File() m, origine = 1, 2 # À compléter : n - 1 fois, enfiler les multiples de m selon son origine, # puis prendre le plus petit nombre en tête de file et le défiler return m #--- correction def hamming2(n): """Même résultat que hamming(n), sans doublon dans les files.""" f2 = File() f3 = File() f5 = File() m, origine = 1, 2 for i in range(n - 1): if origine == 2: f2.enfile(2 * m) if origine in (2, 3): f3.enfile(3 * m) f5.enfile(5 * m) tetes = [(f.tete(), k) for f, k in ((f2, 2), (f3, 3), (f5, 5)) if f.taille() > 0] m, origine = min(tetes) {2: f2, 3: f3, 5: f5}[origine].defile() return m print([hamming2(i) for i in range(1, 31)]) #--- tests assert all(hamming2(i) == hamming(i) for i in range(1, 300)), "hamming2 doit donner les mêmes valeurs que hamming" assert hamming2(2002) == 8153726976, "hamming2(2002) doit valoir 8153726976" ``` ## 🧠 À retenir - Les **piles** (LIFO) et **files** (FIFO) sont essentielles pour : - l’évaluation d’expressions, - les parcours de graphes, - la génération structurée de solutions. - Elles permettent d’implémenter des parcours **sans récursivité explicite**. - Ces mécanismes sont au cœur des algorithmes de graphes (BFS, DFS). %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]] %% nav-fin %% --- 🗓️ Historique Dernière mise à jour : `8 novembre 2026` Rédigé par : [[Julien DUQUENNOY]]