Chapitre 3 - Entraînement : Structures de données linéaires

---

Structures linéaires

Exercice 1 - Pile : vérification de parenthèses

Écrire une fonction parentheses_valides(expression) qui vérifie si les parenthèses, crochets et accolades d'une expression sont correctement équilibrés, en utilisant une pile.

Exemples :

• "(3 + [5 - 2]) * {1 + 1}" → True
• "(3 + [5)" → False (crochet fermé par une parenthèse)
• "3 + 5) * 2" → False

Solution

def parentheses_valides(expression):
    pile = []
    correspondance = {')': '(', ']': '[', '}': '{'}
    for c in expression:
        if c in "([{":
            pile.append(c)
        elif c in ")]}":
            if len(pile) == 0 or pile[-1] != correspondance[c]:
                return False
            pile.pop()
    return len(pile) == 0

print(parentheses_valides("(3 + [5 - 2]) * {1 + 1}"))  # True
print(parentheses_valides("(3 + [5)"))                   # False
print(parentheses_valides("3 + 5) * 2"))                 # False

---

Exercice 2 - Pile : notation polonaise inversée

En notation polonaise inversée (NPI), les opérateurs sont placés après leurs opérandes :

• 3 4 + signifie 3 + 4 = 7
• 3 4 + 2 * signifie (3 + 4) * 2 = 14

Écrire une fonction evaluer_npi(expression) qui évalue une expression en NPI en utilisant une pile.

Solution

def evaluer_npi(expression):
    pile = []
    for token in expression.split():
        if token in "+-*/":
            b = pile.pop()
            a = pile.pop()
            if token == '+': pile.append(a + b)
            elif token == '-': pile.append(a - b)
            elif token == '*': pile.append(a * b)
            elif token == '/': pile.append(a / b)
        else:
            pile.append(float(token))
    return pile[0]

print(evaluer_npi("3 4 +"))              # 7.0
print(evaluer_npi("3 4 + 2 *"))          # 14.0
print(evaluer_npi("5 1 2 + 4 * + 3 -"))  # 14.0

---

Exercice 3 - File : simulation d'une file d'attente

Écrire une classe FileAttente avec les méthodes arrivee(nom), service(), attente() et afficher(). Simuler : Alice arrive, Bob arrive, Alice est servie, Clara arrive, Bob est servi.

Solution

class FileAttente:
    def __init__(self):
        self.personnes = []

    def arrivee(self, nom):
        self.personnes.append(nom)

    def service(self):
        if len(self.personnes) == 0:
            return None
        return self.personnes.pop(0)

    def attente(self):
        return len(self.personnes)

    def afficher(self):
        if len(self.personnes) == 0:
            print("File vide")
        else:
            print(" ← ".join(self.personnes))

f = FileAttente()
f.arrivee("Alice")
f.arrivee("Bob")
f.afficher()         # Alice ← Bob
print(f.service())   # Alice
f.arrivee("Clara")
f.afficher()         # Bob ← Clara
print(f.service())   # Bob

---

Exercice 4 - Liste chaînée : opérations

Compléter la classe ListeChainee avec :

a. element(i) : renvoie la valeur à l'indice i.

b. supprimer_en_tete() : supprime le premier maillon.

c. inserer_apres(valeur, nouvelle_valeur) : insère un maillon après le premier maillon contenant valeur.

Solution

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

class ListeChainee:
    def __init__(self):
        self.tete = None

    def ajouter_en_tete(self, valeur):
        self.tete = Maillon(valeur, self.tete)

    def element(self, i):
        courant = self.tete
        for _ in range(i):
            courant = courant.suivant
        return courant.valeur

    def supprimer_en_tete(self):
        assert self.tete is not None, "Liste vide"
        valeur = self.tete.valeur
        self.tete = self.tete.suivant
        return valeur

    def inserer_apres(self, valeur, nouvelle_valeur):
        courant = self.tete
        while courant is not None:
            if courant.valeur == valeur:
                nouveau = Maillon(nouvelle_valeur, courant.suivant)
                courant.suivant = nouveau
                return
            courant = courant.suivant

lst = ListeChainee()
for v in [30, 20, 10]:
    lst.ajouter_en_tete(v)
print(lst.element(0))  # 10
print(lst.element(2))  # 30
lst.inserer_apres(20, 25)
print(lst.element(2))  # 25

---

Activités

Activité 1 - Deux implémentations d'une pile

Implémenter la même interface de pile de deux manières différentes : avec un tableau Python (list) et avec une liste chaînée. Vérifier qu'elles se comportent de manière identique sur un même scénario de test.

Solution

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

class PileTableau:
    def __init__(self):
        self.elements = []
    def empiler(self, x):
        self.elements.append(x)
    def depiler(self):
        return self.elements.pop()
    def est_vide(self):
        return len(self.elements) == 0
    def sommet(self):
        return self.elements[-1]

class PileChainee:
    def __init__(self):
        self.tete = None
    def empiler(self, x):
        self.tete = Maillon(x, self.tete)
    def depiler(self):
        val = self.tete.valeur
        self.tete = self.tete.suivant
        return val
    def est_vide(self):
        return self.tete is None
    def sommet(self):
        return self.tete.valeur

def tester_pile(pile, nom):
    print(f"--- Test {nom} ---")
    pile.empiler(10)
    pile.empiler(20)
    pile.empiler(30)
    print(f"Sommet : {pile.sommet()}")
    print(f"Dépiler : {pile.depiler()}")
    print(f"Dépiler : {pile.depiler()}")
    print(f"Vide ? {pile.est_vide()}")
    print(f"Dépiler : {pile.depiler()}")
    print(f"Vide ? {pile.est_vide()}")

tester_pile(PileTableau(), "PileTableau")
tester_pile(PileChainee(), "PileChainee")

---

Projet

Projet - Gestionnaire de tâches avec priorités

Créer un gestionnaire de tâches utilisant :

• une file de priorité (les tâches les plus urgentes sont traitées en premier) ;
• une pile pour l'historique des tâches terminées (annulation possible) ;
• un dictionnaire pour stocker les détails de chaque tâche.

Fonctionnalités : ajouter une tâche (nom, priorité, description), traiter la tâche la plus urgente, annuler le dernier traitement, afficher les tâches en attente et l'historique.

Solution

class Tache:
    def __init__(self, nom, priorite, description):
        self.nom = nom
        self.priorite = priorite
        self.description = description

    def __str__(self):
        return f"[P{self.priorite}] {self.nom} : {self.description}"

class GestionnaireTaches:
    def __init__(self):
        self.en_attente = []
        self.historique = []

    def ajouter(self, nom, priorite, description):
        tache = Tache(nom, priorite, description)
        self.en_attente.append(tache)
        self.en_attente.sort(key=lambda t: t.priorite)
        print(f"Tâche ajoutée : {tache}")

    def traiter(self):
        if len(self.en_attente) == 0:
            print("Aucune tâche en attente.")
            return
        tache = self.en_attente.pop(0)
        self.historique.append(tache)
        print(f"Tâche traitée : {tache}")

    def annuler(self):
        if len(self.historique) == 0:
            print("Aucune tâche à annuler.")
            return
        tache = self.historique.pop()
        self.en_attente.append(tache)
        self.en_attente.sort(key=lambda t: t.priorite)
        print(f"Annulation : {tache} remise en attente")

    def afficher_attente(self):
        print("--- Tâches en attente ---")
        if len(self.en_attente) == 0:
            print("  (aucune)")
        for t in self.en_attente:
            print(f"  {t}")

    def afficher_historique(self):
        print("--- Historique (plus récent en haut) ---")
        if len(self.historique) == 0:
            print("  (vide)")
        for t in reversed(self.historique):
            print(f"  {t}")

g = GestionnaireTaches()
g.ajouter("Bug critique", 1, "Corriger le crash au démarrage")
g.ajouter("Documentation", 3, "Écrire le README")
g.ajouter("Nouvelle fonctionnalité", 2, "Ajouter le mode sombre")
g.afficher_attente()
g.traiter()
g.traiter()
g.afficher_historique()
g.annuler()
g.afficher_attente()