Devoir sur les piles

L'usage de la calculatrice n'est pas autorisé.

Le barème est donné à titre indicatif

Durée : 55 min

Exercice 1 (9 points)

Cet exercice traite des notions de piles et de programmation orientée objet.

On crée une classe Pile qui modélise la structure d'une pile d'entiers.

Le constructeur de la classe initialise une pile vide.

La définition de cette classe sans l’implémentation de ses méthodes est donnée ci-dessous.

class Pile:

def __init__(self):
"""Initialise la pile comme une pile vide."""

def est_vide(self):
"""Renvoie True si la liste est vide, False sinon."""

def empiler(self, e):
"""Ajoute l'élément e sur le sommet de la pile, ne renvoie rien."""

def depiler(self):
"""Retire l’élément au sommet de la pile et le renvoie."""

def nb_elements(self):
"""Renvoie le nombre d'éléments de la pile. """

def afficher(self):
"""Affiche de gauche à droite les éléments de la pile, du fond de la pile vers son sommet. 
Le sommet est alors l’élément affiché le plus à droite. Les éléments sont séparés par une virgule.
Si la pile est vide la méthode affiche « pile vide »."""

Seules les méthodes de la classe ci-dessus doivent être utilisées pour manipuler les objets Pile.

a. Écrire une suite d’instructions permettant de créer une instance de la classe Pile affectée à une variable pile1 contenant les éléments 7, 5 et 2 insérés dans cet ordre.

Ainsi, à l'issue de ces instructions, pile1.afficher() produit l’affichage : 7, 5, 2.

b. Donner l’affichage produit après l’exécution des instructions suivantes.
```
element1 = pile1.depiler() 
pile1.empiler(5) 
pile1.empiler(element1) 
pile1.afficher()
```
Correction

a.
```
pile1=Pile()
pile1.empiler(7)
pile1.empiler(5)
pile1.empiler(2)
```
b. 7,5,5,2

On donne la fonction mystere suivante :

def mystere(pile, element): 
    pile2 = Pile()
    nb_elements = pile.nb_elements() 
    for i in range(nb_elements):
        elem = pile.depiler() 
        pile2.empiler(elem) 
        if elem == element:
            return pile2 
    return pile2

a. Dans chacun des quatre cas suivants, quel est l’affichage obtenu dans la console ?

Cas n°1

>>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 2).afficher()

Correction

3,2

Cas n°2

>>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 9).afficher()

Correction

3, 2, 5, 7

Cas n°3

>>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 3).afficher()

Correction

3

Cas n°4

>>>pile.est_vide() 
True
>>>mystere(pile, 3).afficher()

Correction

"pile vide"

b. Expliquer ce que permet d'obtenir la fonction mystere.

Correction

La fonction mystere retourne la pile inversée si elle ne contient pas element. sinon, elle retourne sa partie supérieure inversée, jusqu'à element

Écrire une fonction etendre(pile1, pile2) qui prend en arguments deux objets Pile appelés pile1 et pile2 et qui modifie pile1 en lui ajoutant les éléments de pile2 rangés dans l'ordre inverse. Cette fonction ne renvoie rien.

On donne ci-dessous les résultats attendus pour certaines instructions.
```
>>>pile1.afficher() 
7, 5, 2, 3
>>>pile2.afficher() 
1, 3, 4
>>>etendre(pile1, pile2)
>>>pile1.afficher() 
7, 5, 2, 3, 4, 3, 1
>>>pile2.est_vide() 
True
```
Correction
```
def etendre(pile1,pile2):
    while not pile2.est_vide():
        pile1.empiler(pile2.depiler())
```

Écrire une fonction supprime_toutes_occurences(pile, element) qui prend en arguments un objet Pile appelé pile et un élément element et supprime tous les éléments element de pile.

On donne ci-dessous les résultats attendus pour certaines instructions.

>>>pile.afficher() 
7, 5, 2, 3, 5
>>>supprime_toutes_occurences (pile, 5)
>>>pile.afficher() 
7, 2, 3

Correction

def supprime_toutes_occurences(pile, element):
    pile2=Pile()
    while not pile.est_vide():
        elem=pile.depiler()
        if elem != element:
            pile2.empiler(elem)
    while not pile2.est_vide():
        pile.empiler(pile2.depiler())

Exercice 2 (3 points)

Écrire une fonction renverse qui prend une chaîne de caractères en argument, qui utilise une pile (on pourra utiliser les méthodes de l'exercice 1) pour intervertir les mots de la chaîne, et retourne la chaîne renversée.

L'utilisation de reverse ou split n'est pas autorisée.

Exemple

>>> renverse("vive la frite")
"frite la vive"

Correction

def renverse(chaine):
    pile=Pile()
    res=""
    i=0
    while i<len(chaine):
        mot=""
        while i<len(chaine) and chaine[i] !=" ":
            mot=mot+chaine[i]
            i=i+1
        pile.empiler(mot)
        i=i+1
    while not pile.est_vide():
        res=res+pile.depiler()+" "
    return res[0:-1]