Formation I.S.N.

Pile

Une pile en python avec une liste

Une pile est une structure de données abstraite.

Si l'on reprend l'idée "donnée = assiette", une pile est semblable à une pile d'assiettes et l'on précise les opérations permises:

  • On peut empiler une assiette (ajouter une assiette en haut de pile)
  • On peut dépiler une assiette (enlever l'assiette en haut de pile).
  • On peut savoir si la pile est vide ou non.

Par contre, on ne peut pas, comme dans une liste, prendre une assiette à n'importe quel rang dans la pile (on risquerait de tout faire tomber et de casser toutes les assiettes), ni ajouter une assiette n'importe où dans la pile.

Pour implémenter une pile en python, on peut utiliser le type liste. Et pour interdire d'autres opérations que celles signalées ci-dessus, on peut définir une classe pile (voir la capsule d'initiation à la syntaxe POO en python) dont les méthodes correspondront à nos opérations. Nous ajoutons ici une méthode d'affichage pour les tests (l'affichage de la pile est en général inutile dans les algorithmes utilisant la structure de pile): 



class Pile:
	
	def __init__(self):
		self.valeurs = []
		
	def empiler(self, valeur):
		self.valeurs.append(valeur)
		
	def depiler(self):
		if self.valeurs:
			return self.valeurs.pop()
			
	def estVide(self):
		return self.valeurs == []
		
	
	def __str__(self):
		ch = ''
		for x in self.valeurs:
			ch = "|\t" + str(x) + "\t|" + "\n" + ch
		ch = "\nEtat de la pile:\n" + ch
		return ch
			
			
			
p = Pile()
p.empiler(9)
p.empiler(2)
p.empiler(5)

print(p)

p.depiler()
p.empiler(7)

print(p.estVide())

print(p)

L'affichage obtenu est ici (avec les lignes 31, 36 et 38):

Etat de la pile:
|	5	|
|	2	|
|	9	|

False

Etat de la pile:
|	7	|
|	2	|
|	9	|

On ajoute aussi souvent une fonction pour lire la valeur au sommet de la pile (sans dépiler) et parfois la possibilité de connaître le nombre d'éléments dans la pile:


class Pile:
	
	def __init__(self):
		self.valeurs = []
		
	def empiler(self, valeur):
		self.valeurs.append(valeur)
		
	def depiler(self):
		if self.valeurs:
			return self.valeurs.pop()
			
	def estVide(self):
		return self.valeurs == []
		
	def nombreDAssiettes(self):
		return len(self.valeurs)
		
	def lireSommet(self):
		return self.valeurs[-1]
		
	
	def __str__(self):
		ch = ''
		for x in self.valeurs:
			ch = "|\t" + str(x) + "\t|" + "\n" + ch
		ch = "\nEtat de la pile:\n" + ch
		return ch
			
			
			
p = Pile()
p.empiler(9)
p.empiler(2)
p.empiler(5)
 
print(p)
print(p.lireSommet())
print(p.nombreDAssiettes())

L'affichage obtenu:

Etat de la pile:
|	5	|
|	2	|
|	9	|

5
3

Une pile en python avec une liste chaînée

Le principe de la liste chaînée est encore plus adapté pour l'implémentation d'une liste.

Vous pouvez chercher sur le web la notion de liste chaînée si vous ne connaissez pas. L'idée est d'utiliser une suite de maillons, chaque maillon contenant d'une part une donnée et d'autre part un lien sur le maillon suivant de la chaîne.

Une représentation classique est la suivante:
Représentation d'une liste chaînée.
Chaque boîte contient une donnée, la flèche à droite de la boîte est le lien sur la donnée suivante, le dernier maillon ne pointe sur rien (on utilisera None en python). La première flèche à gauche peut être associée dans le code python ci-dessous à la variable p (la variable p de type Pile "pointe" sur le premier maillon et permet de le récupérer avec la syntaxe p.sommet).

Un code possible:


class Maillon:
	
	def __init__(self, valeur, suivant=None):
		self.valeur = valeur
		self.suivant = suivant
		
		
		
class Pile:

	def __init__(self):
		self.taille = 0 # nombre d'assiettes dans la pile
		self.sommet = None  
		
		
	def empiler(self, valeur):
		self.sommet = Maillon(valeur, self.sommet)
		self.taille += 1
		
	def depiler(self):
		if self.taille > 0:
			valeur = self.sommet.valeur
			self.sommet = self.sommet.suivant
			self.taille -= 1
			return valeur
			
	def estVide(self):
		return self.taille == 0
		

	def lireSommet(self):
		return self.sommet.valeur
		
	
	def __str__(self):
		ch = "\nEtat de la pile:\n"
		sommet = self.sommet
		while sommet != None:
			ch += "|\t" + str(sommet.valeur) + "\t|" + "\n"  
			sommet = sommet.suivant
		  
		return ch
			
			
			
p = Pile()
p.empiler(9)
p.empiler(2)
p.empiler(5)
 
print(p)
print(p.lireSommet())
print(p.taille)


p.depiler()
p.depiler()
p.empiler(8)

print(p)
print(p.lireSommet())
print(p.taille)

L'affichage obtenu:

Etat de la pile:
|	5	|
|	2	|
|	9	|

5
3

Etat de la pile:
|	8	|
|	9	|

8
2

La polonaise

Dans l'écriture usuelle des expressions algébriques, les parenthèses sont indispensables. Elles permettent par exemple de distinguer les expressions \( 1 + 2\times 3 \) et \( (1+2)\times 3 \).

Avec la notation préfixée (appelée aussi notation polonaise, en référence à un mathématicien polonais, Jan Lukasiewic), les parenthèses ne sont plus nécessaires :

  • 1 + 2* 3 = + 1 * 2 3
  • (1+2) * 3 = * + 1 2 3

Stockons une expression en notation polonaise dans une liste. Par exemple, l'expression "+ * - / 10 2 4 3 6" est stockée dans la liste ['+', '*', '-', '/', 10, 2, 4, 3, 6].

Pour évaluer cette expression, on utilisera une pile. On parcourt la liste de la fin vers le début:

  1. si l'élément est un nombre, on l'empile.
  2. Si l'élément est un opérateur, on dépile ses deux opérandes et on calcule, puis on empile le résultat de ce calcul.

Le résultat de l'expression est l'unique élément restant dans la pile.

Écrire une telle fonction d'évaluation.

  • un code possible
  • avec affichage

class Maillon:
	
	def __init__(self, valeur, suivant=None):
		self.valeur = valeur
		self.suivant = suivant
		
		
		
class Pile:

	def __init__(self):
		self.taille = 0 # nombre d'assiettes dans la pile
		self.sommet = None  
		
		
	def empiler(self, valeur):
		self.sommet = Maillon(valeur, self.sommet)
		self.taille += 1
		
	def depiler(self):
		if self.taille > 0:
			valeur = self.sommet.valeur
			self.sommet = self.sommet.suivant
			self.taille -= 1
			return valeur
			
	def estVide(self):
		return self.taille == 0
		
 	
			
def prefixe(expression):
	pile = Pile()
	for c in reversed(expression):
		if isinstance(c, int):
			pile.empiler(c)
		else:
			a = pile.depiler()
			b = pile.depiler()
			pile.empiler(eval(str(a) + c + str(b)))
	return pile.depiler()
	
 
	
r = prefixe(['+', '*', '-', '/', 10, 2, 4, 3, 6])
print(r)


class Maillon:
	
	def __init__(self, valeur, suivant=None):
		self.valeur = valeur
		self.suivant = suivant
		
		
		
class Pile:

	def __init__(self):
		self.taille = 0 # nombre d'assiettes dans la pile
		self.sommet = None  
		
		
	def empiler(self, valeur):
		self.sommet = Maillon(valeur, self.sommet)
		self.taille += 1
		
	def depiler(self):
		if self.taille > 0:
			valeur = self.sommet.valeur
			self.sommet = self.sommet.suivant
			self.taille -= 1
			return valeur
			
	def estVide(self):
		return self.taille == 0
		
 
		
	
	def __str__(self):
		ch = "\nEtat de la pile:\n"
		sommet = self.sommet
		while sommet != None:
			ch += "|\t" + str(sommet.valeur) + "\t|" + "\n"  
			sommet = sommet.suivant
		  
		return ch
			
			
			
 
	
	
def prefixe(expression):
	pile = Pile()
	for c in reversed(expression):
		if isinstance(c, int):
			pile.empiler(c)
			print(pile)
		else:
			a = pile.depiler()
			b = pile.depiler()
			pile.empiler(eval(str(a) + c + str(b)))
			print(pile)
	return pile.depiler()
	
	
r = prefixe(['+', '*', '-', '/', 10, 2, 4, 3, 6])
print(r)

L'affichage obtenu: 

Etat de la pile:
|	6	|


Etat de la pile:
|	3	|
|	6	|


Etat de la pile:
|	4	|
|	3	|
|	6	|


Etat de la pile:
|	2	|
|	4	|
|	3	|
|	6	|


Etat de la pile:
|	10	|
|	2	|
|	4	|
|	3	|
|	6	|


Etat de la pile:
|	5.0	|
|	4	|
|	3	|
|	6	|


Etat de la pile:
|	1.0	|
|	3	|
|	6	|


Etat de la pile:
|	3.0	|
|	6	|


Etat de la pile:
|	9.0	|

9.0