# Piles et Files
## 🎯 Objectif
Mettre en œuvre des **structures de données fondamentales** (pile et file) afin de résoudre des problèmes algorithmiques classiques liés aux **graphes et parcours implicites**.
## 📄 É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 les **structures pile et file** permettent de parcourir et traiter des données de manière systématique, sans récursivité explicite.
## 🧩 Travail demandé
### Partie 1 – Pile et notation polonaise inverse
1. Implémenter une structure de **pile**.
2. Évaluer une expression écrite en **notation polonaise inverse (NPI)**.
3. Afficher l’évolution de la pile au cours du calcul.
### Partie 2 – File et suite de Hamming
1. Implémenter une structure de **file**.
2. Générer les nombres de la **suite de Hamming**.
3. Comprendre le rôle des files dans l’exploration progressive des valeurs.
## đź“Ž Support de travail
- 💾 **Notebook – Notation Polonaise Inverse (pile)**
đź”— [ressource](https://github.com/unilasalle-apex/Python/blob/main/Notation_Polonaise_Inverse.ipynb)
- 💾 **Notebook – Suite de Hamming (files)**
đź”— [ressource](https://github.com/unilasalle-apex/Python/blob/main/La_suite_de_Hamming.ipynb)
## ✅ Corrigés
>[!success]- ✅ Corrigé 1 — Pile et notation polonaise inverse
>```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):
> out = str(self.elements[0])
> for x in self.elements[1:]:
> out = str(x) + " -> " + out
> out = "Pile : " + out
> return out
>
>
>def est_Operateur(x):
> return x in '+-*/'
>
>
>def calcul(op, m, n):
> if op == '+':
> return n + m
> elif op == '-':
> return n - m
> elif op == '*':
> return n * m
> else:
> return n / m
>
>
>s = '5 8 3 - * 3 * 3 1 - 2 * 3 / +'
>
>
>def calcul_NPI(s):
> e = s.split()
> p = Pile()
> for i in e:
> if p.taille() > 0:
> print(p)
> if est_Operateur(i):
> p.empile(calcul(i, p.depile(), p.depile()))
> else:
> p.empile(int(i))
> return p.depile()
>
>
>print(calcul_NPI(s))
>```
>[!success]- ✅ Corrigé 2 — File et suite de Hamming
>```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 sommet(self):
> if len(self.elements) == 0:
> raise Exception("La file est vide")
> return self.elements[0]
>
> def __str__(self):
> out = str(self.elements[0])
> for x in self.elements[1:]:
> out = str(x) + " -> " + out
> out = "File : " + out
> return out
>
>
>f2 = File()
>f3 = File()
>f5 = File()
>
>f2.enfile(1)
>f3.enfile(1)
>f5.enfile(1)
>
>
>def hamming(n):
> for i in range(n):
> m = min(f2.sommet(), f3.sommet(), f5.sommet())
> if m == f2.sommet():
> f2.defile()
> if m == f3.sommet():
> f3.defile()
> if m == f5.sommet():
> f5.defile()
> f2.enfile(2 * m)
> f3.enfile(3 * m)
> f5.enfile(5 * m)
> return m
>
>
>hamming(2002)
>```
## 🧠À 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).
## 🗓️ Historique
- **Créé le :** 05 février 2026
- **Auteur :** [[Julien DUQUENNOY]]