TP : Implémentation et Applications

Objectif

Implémenter les structures de données Pile et File en POO et les utiliser pour résoudre des problèmes classiques.

Partie 1 : Implémentation

À faire

Implémentez les classes Pile et File vues en cours. Ajoutez une méthode __str__ pour visualiser le contenu de la structure (ex: [1, 2, 3]).

Partie 2 : Application des Piles - Vérification de parenthèses

On veut vérifier si une expression mathématique est bien parenthésée. Exemple valide : (a + (b * c)) Exemple invalide : (a + b)), ((a+b), )a+b(

Algorithme :

Parcourir la chaîne de caractères.
Si on rencontre (, on l'empile.
Si on rencontre ), on dépile.
- Si la pile est vide (rien à dépiler), c'est une erreur (parenthèse fermante en trop).
À la fin, la pile doit être vide (toutes les parenthèses ouvertes ont été fermées).

Exercice

Écrivez la fonction verifier_parentheses(expression) qui retourne True ou False.

def verifier_parentheses(expression):
    p = Pile()
    for caractere in expression:
        if caractere == '(':
            p.empiler(caractere)
        elif caractere == ')':
            if p.est_vide():
                return False
            p.depiler()
    return p.est_vide()

# Tests
print(verifier_parentheses("(a+b)"))      # True
print(verifier_parentheses("((a+b)*c)"))  # True
print(verifier_parentheses("(a+b))"))     # False
print(verifier_parentheses("((a+b)"))     # False

Partie 3 : Application des Files - Simulation

On veut simuler une file d'attente d'impression. Des documents arrivent (nom du fichier) et sont mis en file d'attente. L'imprimante traite les documents un par un.