TP1 Conception d’algorithmes
Dr. Kaoutar SENHAJI
8 octobre 2024
Introduction
Ce TP a pour but de découvrir la programmation orientée objet en Py-
thon. Nous allons explorer plusieurs concepts, tels que :
— Les classes et objets en Python.
— Les constructeurs et destructeurs.
— L’opérateur d’affectation et le constructeur de copie.
— La surcharge d’opérateurs.
— L’utilisation d’une pile en programmation.
1 Notion de Pile
Une pile (“stack” en anglais) est une structure de données basée sur le
principe “Dernier arrivé, premier sorti” (LIFO). Le dernier élément ajouté à
la pile sera le premier à être récupéré.
Voici quelques fonctions communément utilisées pour manipuler des piles :
— Empiler : ajoute un élément à la pile.
— Dépiler : enlève un élément de la pile et le renvoie.
— La pile est-elle vide ? : renvoie “vrai” si la pile est vide, “faux” sinon.
— La pile est-elle pleine ? : renvoie “vrai” si la pile est pleine, “faux”
sinon.
— Nombre d’éléments dans la pile : renvoie le nombre d’éléments
présents dans la pile.
2 Classe PileChar
Le but est de réaliser une classe Python représentant une pile de carac-
tères. Voici la classe à implémenter :
1
Listing 1 – Classe PileChar en Python
class PileChar :
def __init__ ( s e l f , t a i l l e =50):
s e l f .max = t a i l l e
s e l f . sommet = 0
self . pile = []
def e m p i l e r ( s e l f , c ) :
if s e l f . estPleine ():
r a i s e Ex cep ti on ( " P i l e ␣ p l e i n e ␣ ! " )
s e l f . p i l e . append ( c )
s e l f . sommet += 1
def d e p i l e r ( s e l f ) :
i f s e l f . estVide ( ) :
r a i s e Ex cep ti on ( " P i l e ␣ v i d e ␣ ! " )
s e l f . sommet −= 1
return s e l f . p i l e . pop ( )
def e s t V i d e ( s e l f ) :
return s e l f . sommet == 0
def e s t P l e i n e ( s e l f ) :
return s e l f . sommet == s e l f .max
def t a i l l e ( s e l f ) :
return s e l f .max
def compter ( s e l f ) :
return s e l f . sommet
def a f f i c h e r ( s e l f ) :
print ( f " [ { ’ ’ . j o i n ( s e l f . p i l e ) } ] " )
# Exemple d ’ u t i l i s a t i o n
p i l e = PileChar (5)
p i l e . empiler ( ’a ’ )
p i l e . empiler ( ’b ’ )
p i l e . empiler ( ’ c ’ )
p i l e . a f f i c h e r ( ) # A f f i c h e r a : [ abc ]
2
print ( p i l e . d e p i l e r ( ) ) # A f f i c h e r a : c
p i l e . a f f i c h e r ( ) # A f f i c h e r a : [ ab ]
3 Exercices
Exercice 1 : Implémentation de la méthode afficher
Ajoutez une méthode afficher à la classe PileChar pour afficher les élé-
ments de la pile entre crochets (comme dans l’exemple d’utilisation). Testez
cette méthode en empilant et dépilant des caractères.
Exercice 2 : Gestion d’une pile pleine
Modifiez la méthode empiler pour renvoyer un message d’erreur au lieu de
lever une exception en cas de pile pleine.
Exercice 3 : Comparaison de piles
Surchargez l’opérateur == pour permettre la comparaison de deux piles PileChar.
Deux piles sont égales si elles ont le même contenu et la même taille.
class PileChar :
# ( M thodes p r c d e n t e s . . . )
def __eq__( s e l f , o t h e r ) :
return s e l f . p i l e == o t h e r . p i l e
p i l e 1 = PileChar (5)
p i l e 2 = PileChar (5)
print ( p i l e 1 == p i l e 2 ) # A f f i c h e r a True s i l e s deux p i l e s s o n t gales
Exercice 4 : Copie de pile
En utilisant le module copy, implémentez la fonctionnalité de copie d’une pile
PileChar. Utilisez une copie profonde pour éviter les références partagées
entre les objets.
import copy
p i l e 1 = PileChar (5)
p i l e 2 = copy . deepcopy ( p i l e 1 )
Exercice 5 : Gestion des erreurs
Ajoutez des tests supplémentaires dans vos méthodes pour vérifier les er-
reurs possibles, comme le fait de dépiler une pile vide. Affichez des messages
d’avertissement appropriés.
Exercice 6 : Empilage de chaînes de caractères
Modifiez votre classe pour accepter des chaînes de caractères complètes au
3
lieu de simples caractères. Empilez plusieurs mots et affichez-les dans l’ordre
inverse grâce à la méthode depiler.
Exercice 7 : Pile générique
Modifiez la classe pour qu’elle puisse accepter n’importe quel type d’objet
(entiers, chaînes, objets, etc.). Testez en empilant différents types de données
et en les dépilant.
Exercice 8 : Test de palindrome
Écrivez une fonction qui utilise une pile pour vérifier si une chaîne de carac-
tères est un palindrome (un mot qui se lit de la même façon dans les deux
sens). Utilisez les méthodes empiler et depiler.
def est_palindrome ( mot ) :
p i l e = P i l e C h a r ( len ( mot ) )
for char in mot :
p i l e . e m p i l e r ( char )
mot_inverse = ’ ’ . j o i n ( [ p i l e . d e p i l e r ( ) for _ in range ( len ( mot ) ) ] )
return mot == mot_inverse
mot = " r a d a r "
print ( est_palindrome ( mot ) ) # A f f i c h e r a True s i c ’ e s t un p a l i n d r o m e
Exercice 9 : Simulation de la tour de Hanoï
Créez un programme simulant la tour de Hanoï avec des piles. Vous devrez
manipuler plusieurs piles pour déplacer les disques d’une pile à une autre,
selon les règles du jeu.
Exercice 10 : Représentation graphique de la pile
Imprimez la pile verticalement pour représenter chaque élément sur une nou-
velle ligne. Par exemple :
-----
c
b
a
-----
4 Conclusion
Ce TP vous a permis de manipuler les concepts de la programmation
orientée objet en Python à travers l’implémentation et la gestion d’une struc-
ture de pile. Vous avez exploré plusieurs aspects tels que les méthodes d’une
classe, la gestion des erreurs, la surcharge d’opérateurs et la copie d’objets.
