Filtre des nombres positifs d'une pile⚓︎
On donne une mise en œuvre simple de la structure de Pile avec les listes Python.
class Pile:
"Classe à ne pas modifier"
def __init__(self, valeurs=None):
"""Initialise une pile
- vide, si `valeurs` n'est pas fourni ;
- remplie avec `valeurs` sinon.
- Le sommet de la pile est à la fin de la liste.
"""
if valeurs is None:
self.valeurs = []
else:
self.valeurs = valeurs
def est_vide(self):
"Renvoie un booléen : la pile est-elle vide ?"
return self.valeurs == []
def __str__(self):
"Affiche la pile, en indiquant le sommet"
return "| " + " | ".join(map(str, self.valeurs)) + ' <- sommet'
def depile(self):
"""
- Si la pile est vide, provoque une erreur.
- Sinon, dépile un élément au sommet et le renvoie.
"""
if self.est_vide():
raise ValueError("Erreur, pile vide")
else:
return self.valeurs.pop()
def empile(self, element):
"Empile un élément au sommet de la pile"
self.valeurs.append(element)
Pour cet exercice, on n'utilisera que les méthodes de la classe Pile
et non les méthodes des listes Python. À savoir, uniquement :
- Avec
pile
qui est un objet de la classePile
,pile.empile(element)
; empile unelement
au sommet depile
,pile.depile()
; dépile et renvoieelement
au sommet depile
qui est non vide.
Écrire une fonction filtre_positif
qui prend en paramètre donnees
de type Pile
d'entiers et qui renvoie une pile qui contient les éléments positifs de donnees
. La pile donnees
doit être globalement inchangée.
Exemples
>>> donnees = Pile([4, -11, 7, -3, -1, 0, 6])
>>> print(filtre_positifs(donnees))
| 4 | 7 | 0 | 6 <- sommet
>>> print(donnees)
| 4 | -11 | 7 | -3 | -1 | 0 | 6 <- sommet
>>> donnees = Pile([1, 2, 3, 4])
>>> print(filtre_positifs(donnees))
| 1 | 2 | 3 | 4 <- sommet
>>> print(donnees)
| 1 | 2 | 3 | 4 <- sommet
>>> donnees = Pile([-4, -3, -2, -1])
>>> print(filtre_positifs(donnees))
| <- sommet
>>> print(donnees)
| -4 | -3 | -2 | -1 <- sommet
#--- HDR ---#bksl-nlbksl-nlclass Pile:bksl-nl "Classe à ne pas modifier"bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs=[]):bksl-nl """Initialise une pilebksl-nl - vide, si valeurs
n'est pas fourni ;bksl-nl - remplie avec valeurs
sinon.bksl-nl - Le sommet de la pile est à la fin de la liste.bksl-nl """bksl-nl self.valeurs = list(valeurs)bksl-nl bksl-nl def estpy-undvide(self):bksl-nl "Renvoie un booléen : la pile est-elle vide ?"bksl-nl return self.valeurs == list()bksl-nl bksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl "Affiche la pile, en indiquant le sommet"bksl-nl return "| " + " | ".join(map(str, self.valeurs)) + ' <- sommet'bksl-nl bksl-nl def depile(self):bksl-nl """bksl-nl - Si la pile est vide, provoque une erreur.bksl-nl - Sinon, dépile un élément au sommet et le renvoie.bksl-nl """bksl-nl if self.estpy-undvide():bksl-nl raise ValueError("Erreur, pile vide")bksl-nl else:bksl-nl return self.valeurs.pop()bksl-nlbksl-nl def empile(self, element):bksl-nl "Empile un élément au sommet de la pile"bksl-nl self.valeurs.append(element)bksl-nl bksl-nl#--- HDR ---#bksl-nl# la classe Pile est utilisable directement pour cet exercicebksl-nlbksl-nldef filtrepy-undpositifs(donnees):bksl-nl "fonction à compléter"bksl-nl auxiliaire = Pile()bksl-nl while not ... .estpy-undvide():bksl-nl element = donnees. ... ()bksl-nl auxiliaire. ...(...)bksl-nl bksl-nl resultat = Pile()bksl-nl while ...:bksl-nl element = ...bksl-nl donnees.empile(element)bksl-nl if element >= 0:bksl-nl ...bksl-nl bksl-nl return ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nldonnees = Pile([4, -11, 7, -3, -1, 0, 6])bksl-nlassert str(filtrepy-undpositifs(donnees)) == '| 4 | 7 | 0 | 6 <- sommet'bksl-nlassert donnees.estpy-undvide() == Falsebksl-nlassert str(donnees) == '| 4 | -11 | 7 | -3 | -1 | 0 | 6 <- sommet'bksl-nlbksl-nldonnees = Pile([1, 2, 3, 4])bksl-nlassert str(filtrepy-undpositifs(donnees)) == '| 1 | 2 | 3 | 4 <- sommet'bksl-nlassert donnees.estpy-undvide() == Falsebksl-nlassert str(donnees) == '| 1 | 2 | 3 | 4 <- sommet'bksl-nlbksl-nldonnees = Pile([-4, -3, -2, -1])bksl-nlassert str(filtrepy-undpositifs(donnees)) == '| <- sommet'bksl-nlassert donnees.estpy-undvide() == Falsebksl-nlassert str(donnees) == '| -4 | -3 | -2 | -1 <- sommet'bksl-nlbksl-nlclass Pile:bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs=[]):bksl-nl self.valeurs = list(valeurs)bksl-nl bksl-nl def estpy-undvide(self):bksl-nl return self.valeurs == list()bksl-nl bksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl "Affiche la pile, en indiquant le sommet"bksl-nl return "| " + " | ".join(map(str, self.valeurs)) + ' <- sommet'bksl-nl bksl-nl def depile(self):bksl-nl if self.estpy-undvide():bksl-nl raise ValueError("Erreur, pile vide")bksl-nl else:bksl-nl return self.valeurs.pop()bksl-nlbksl-nl def empile(self, element):bksl-nl self.valeurs.append(element)bksl-nl bksl-nlbksl-nldef filtrepy-undpositifs(donnees):bksl-nl auxiliaire = Pile()bksl-nl while not donnees.estpy-undvide():bksl-nl element = donnees.depile()bksl-nl auxiliaire.empile(element)bksl-nl bksl-nl resultat = Pile()bksl-nl while not auxiliaire.estpy-undvide():bksl-nl element = auxiliaire.depile()bksl-nl donnees.empile(element)bksl-nl if element >= 0:bksl-nl resultat.empile(element)bksl-nl bksl-nl return resultatbksl-nlbksl-nl
A
Z