L = creer_liste_vide()
L = ajouter_en_tete(10,L)
L = ajouter_en_tete(9,L)
L = ajouter_en_tete(7,L)
L1 = creer_liste_vide()
L2 = construire_liste(5, construire_liste(4, construire_liste(3, construire_liste(2, construire_liste(1, construire_liste(0,L1))))))

def vide():
    return None # Une liste vide est représentée par None

def construire_liste(x, L): # C'est notre 'cons' !
    return (x, L) # Un tuple (élément, reste_de_la_liste)

def ajouter_en_tete(L, x): # Attention, l'ordre des arguments est inversé ici par rapport au texte !
    return construire_liste(x, L) # Crée une NOUVELLE liste avec x en tête

def supprimer_en_tete(L):
    # Renvoie la tête (L[0]) et la queue (L[1])
    # Attention: cette fonction suppose que la liste n'est PAS vide.
    # Dans une vraie implémentation, on ajouterait une vérification.
    return (L[0], L[1])

def est_vide(L):
    return L is None # Une liste est vide si elle est None

def compter_elements(L):
    if est_vide(L):
        return 0
    return 1 + compter_elements(L[1]) # Appel récursif sur la queue de la liste

L = vide()
print(f"L est vide : {est_vide(L)}")

L = construire_liste(5, construire_liste(4, construire_liste(3, construire_liste(2, construire_liste(1, construire_liste(0,L))))))
print(f"L après construction : {L}")
print(f"L est vide : {est_vide(L)}")
print(f"Nombre d'éléments dans L : {compter_elements(L)}")

L = ajouter_en_tete(L, 6) # Attention à l'ordre des arguments L et x ici !
print(f"L après ajout de 6 : {L}")
print(f"Nombre d'éléments dans L : {compter_elements(L)}")

x, L = supprimer_en_tete(L)
print(f"Élément supprimé (x) : {x}")
print(f"L après suppression : {L}")
print(f"Nombre d'éléments dans L : {compter_elements(L)}")

x, L = supprimer_en_tete(L)
print(f"Élément supprimé (x) : {x}")
print(f"L après 2ème suppression : {L}")
print(f"Nombre d'éléments dans L : {compter_elements(L)}")

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L): # C'est notre 'cons' !
    return (x, L)

# --- Fonction à écrire pour l'exercice ---

def creer_liste_numerique(n):
    """
    Renvoie une liste (TAD) contenant les entiers de 1 à n.
    Args:
        n (int): Un entier positif ou nul.
    Returns:
        tuple or None: La liste des entiers de 1 à n.
    """
    if n == 0:
        return vide()
    else:
        # On construit la liste de manière récursive, en ajoutant les nombres
        # du plus grand au plus petit pour obtenir l'ordre croissant à la fin
        # (car 'construire_liste' ajoute en tête)
        return construire_liste(n, creer_liste_numerique(n - 1))

# --- Tests ---
print("Exercice 1 :")
L0 = creer_liste_numerique(0)
print(f"creer_liste_numerique(0) : {L0} (vide si None)") # Attend None
L3 = creer_liste_numerique(3)
print(f"creer_liste_numerique(3) : {L3}") # Attend (3, (2, (1, None)))
L5 = creer_liste_numerique(5)
print(f"creer_liste_numerique(5) : {L5}") # Attend (5, (4, (3, (2, (1, None)))))
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

def supprimer_en_tete(L): # Utile pour la version itérative
    return (L[0], L[1])

# --- Fonctions à écrire pour l'exercice ---

# Version récursive
def afficher_elements_liste_rec(ma_liste):
    """
    Affiche récursivement les éléments d'une liste (TAD).
    Args:
        ma_liste (tuple or None): La liste à afficher.
    """
    if not est_vide(ma_liste):
        print(ma_liste[0], end=" ") # Affiche l'élément actuel
        afficher_elements_liste_rec(ma_liste[1]) # Appel récursif sur la queue
    else:
        print() # Pour le retour à la ligne à la fin

# Version itérative (avec boucle while)
def afficher_elements_liste_iter(ma_liste):
    """
    Affiche itérativement les éléments d'une liste (TAD).
    Args:
        ma_liste (tuple or None): La liste à afficher.
    """
    temp_list = ma_liste # On utilise une variable temporaire pour ne pas modifier la liste originale
    while not est_vide(temp_list):
        print(temp_list[0], end=" ")
        temp_list = temp_list[1] # Passe à l'élément suivant (la queue)
    print() # Pour le retour à la ligne à la fin

# --- Tests ---
print("Exercice 2 :")
L_test = construire_liste(10, construire_liste(20, construire_liste(30, vide())))
print("Affichage récursif :")
afficher_elements_liste_rec(L_test) # Attend : 10 20 30
print("Affichage itératif :")
afficher_elements_liste_iter(L_test) # Attend : 10 20 30

L_vide = vide()
print("Affichage récursif liste vide :")
afficher_elements_liste_rec(L_vide) # Attend un retour à la ligne
print("Affichage itératif liste vide :")
afficher_elements_liste_iter(L_vide) # Attend un retour à la ligne
print("-" * 20)

def obtenir_nieme_element_rec(n, lst):
    """
    Renvoie le n-ième élément de la liste lst.
    Les éléments sont numérotés à partir de 0.
    Args:
        n (int): L'index de l'élément à récupérer.
        lst (tuple or None): La liste.
    Raises:
        IndexError: Si l'indice est invalide (liste trop courte ou liste vide initialement).
    Returns:
        Any: L'élément à l'indice n.
    """
    if lst is None:
        raise IndexError("Indice invalide : la liste est vide ou l'indice est hors limites.")
    if n == 0:
        return lst[0]  # Accède à la tête (valeur)
    else:
        return obtenir_nieme_element_rec(n - 1, lst[1]) # Récursion sur la queue

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# --- Fonction à écrire pour l'exercice ---

def obtenir_nieme_element_iter(n, lst):
    """
    Renvoie le n-ième élément de la liste lst en utilisant une boucle while.
    Les éléments sont numérotés à partir de 0.
    Args:
        n (int): L'index de l'élément à récupérer.
        lst (tuple or None): La liste.
    Raises:
        IndexError: Si l'indice est invalide (liste trop courte ou liste vide initialement).
    Returns:
        Any: L'élément à l'indice n.
    """
    if n < 0:
        raise IndexError("L'indice ne peut pas être négatif.")

    current_list = lst
    current_index = 0

    while not est_vide(current_list):
        if current_index == n:
            return current_list[0] # On a trouvé l'élément !
        current_list = current_list[1] # Passe à l'élément suivant (la queue)
        current_index += 1
    
    # Si la boucle se termine, c'est que l'indice est trop grand ou la liste était vide
    raise IndexError("Indice invalide : la liste est trop courte ou l'indice est hors limites.")

# --- Tests ---
print("Exercice 3 :")
L_test = construire_liste('A', construire_liste('B', construire_liste('C', vide())))
print(f"Liste de test : {L_test}")

print(f"Élément à l'index 0 : {obtenir_nieme_element_iter(0, L_test)}") # Attend 'A'
print(f"Élément à l'index 1 : {obtenir_nieme_element_iter(1, L_test)}") # Attend 'B'
print(f"Élément à l'index 2 : {obtenir_nieme_element_iter(2, L_test)}") # Attend 'C'

try:
    print(f"Élément à l'index 3 : {obtenir_nieme_element_iter(3, L_test)}")
except IndexError as e:
    print(f"Erreur attendue : {e}")

try:
    print(f"Élément à l'index 0 (liste vide) : {obtenir_nieme_element_iter(0, vide())}")
except IndexError as e:
    print(f"Erreur attendue : {e}")

try:
    print(f"Élément à l'index -1 : {obtenir_nieme_element_iter(-1, L_test)}")
except IndexError as e:
    print(f"Erreur attendue : {e}")
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# --- Fonctions à écrire pour l'exercice ---

# Version récursive
def compter_occurrences_rec(valeur, ma_liste):
    """
    Compte récursivement le nombre d'occurrences d'une valeur dans une liste (TAD).
    Args:
        valeur (Any): La valeur à chercher.
        ma_liste (tuple or None): La liste où chercher.
    Returns:
        int: Le nombre d'occurrences.
    """
    if est_vide(ma_liste):
        return 0 # Si la liste est vide, il n'y a pas d'occurrences
    
    # Vérifie si la tête correspond à la valeur
    count = 0
    if ma_liste[0] == valeur:
        count = 1
    
    # Ajoute le compte de la queue de la liste
    return count + compter_occurrences_rec(valeur, ma_liste[1])

# Version itérative (avec boucle while)
def compter_occurrences_iter(valeur, ma_liste):
    """
    Compte itérativement le nombre d'occurrences d'une valeur dans une liste (TAD).
    Args:
        valeur (Any): La valeur à chercher.
        ma_liste (tuple or None): La liste où chercher.
    Returns:
        int: Le nombre d'occurrences.
    """
    count = 0
    current_list = ma_liste
    while not est_vide(current_list):
        if current_list[0] == valeur:
            count += 1
        current_list = current_list[1] # Passe à l'élément suivant
    return count

# --- Tests ---
print("Exercice 4 :")
L_test = construire_liste(1, construire_liste(2, construire_liste(1, construire_liste(3, construire_liste(1, vide())))))
print(f"Liste de test : {L_test}")

print(f"Occurrences de 1 (récursif) : {compter_occurrences_rec(1, L_test)}") # Attend 3
print(f"Occurrences de 2 (récursif) : {compter_occurrences_rec(2, L_test)}") # Attend 1
print(f"Occurrences de 4 (récursif) : {compter_occurrences_rec(4, L_test)}") # Attend 0

print(f"Occurrences de 1 (itératif) : {compter_occurrences_iter(1, L_test)}") # Attend 3
print(f"Occurrences de 2 (itératif) : {compter_occurrences_iter(2, L_test)}") # Attend 1
print(f"Occurrences de 4 (itératif) : {compter_occurrences_iter(4, L_test)}") # Attend 0

print(f"Occurrences dans liste vide : {compter_occurrences_rec(5, vide())}") # Attend 0
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# --- Fonctions à écrire pour l'exercice ---

# Version récursive (fonction auxiliaire nécessaire pour gérer l'index)
def trouver_rang_rec(valeur, ma_liste):
    """
    Renvoie récursivement le rang de la première occurrence d'une valeur.
    Args:
        valeur (Any): La valeur à chercher.
        ma_liste (tuple or None): La liste où chercher.
    Returns:
        int or None: Le rang de la première occurrence ou None si non trouvé.
    """
    def _trouver_rang_aux(valeur, current_list, current_index):
        if est_vide(current_list):
            return None # Si on arrive à la fin de la liste, la valeur n'est pas trouvée
        
        if current_list[0] == valeur:
            return current_index # Si la tête correspond, on renvoie l'index actuel
        
        # Sinon, on cherche dans la queue avec l'index incrémenté
        return _trouver_rang_aux(valeur, current_list[1], current_index + 1)
    
    return _trouver_rang_aux(valeur, ma_liste, 0) # Appel initial avec index 0

# Version itérative (avec boucle while)
def trouver_rang_iter(valeur, ma_liste):
    """
    Renvoie itérativement le rang de la première occurrence d'une valeur.
    Args:
        valeur (Any): La valeur à chercher.
        ma_liste (tuple or None): La liste où chercher.
    Returns:
        int or None: Le rang de la première occurrence ou None si non trouvé.
    """
    current_list = ma_liste
    current_index = 0
    while not est_vide(current_list):
        if current_list[0] == valeur:
            return current_index # On a trouvé, on renvoie l'index
        current_list = current_list[1] # Passe à l'élément suivant
        current_index += 1
    return None # Si la boucle se termine, la valeur n'a pas été trouvée

# --- Tests ---
print("Exercice 5 :")
L_test = construire_liste('pomme', construire_liste('banane', construire_liste('cerise', construire_liste('banane', vide()))))
print(f"Liste de test : {L_test}")

print(f"Rang de 'banane' (récursif) : {trouver_rang_rec('banane', L_test)}") # Attend 1
print(f"Rang de 'pomme' (récursif) : {trouver_rang_rec('pomme', L_test)}") # Attend 0
print(f"Rang de 'fraise' (récursif) : {trouver_rang_rec('fraise', L_test)}") # Attend None

print(f"Rang de 'banane' (itératif) : {trouver_rang_iter('banane', L_test)}") # Attend 1
print(f"Rang de 'pomme' (itératif) : {trouver_rang_iter('pomme', L_test)}") # Attend 0
print(f"Rang de 'fraise' (itératif) : {trouver_rang_iter('fraise', L_test)}") # Attend None

print(f"Rang dans liste vide : {trouver_rang_rec('x', vide())}") # Attend None
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonctions à écrire pour l'exercice ---

def concatener_inverse(l1, l2):
    """
    Renvoie une nouvelle liste qui est la concaténation de l2 à la fin de l1 inversée.
    Ne crée pas l'inverse de l1 explicitement.
    Args:
        l1 (tuple or None): La première liste.
        l2 (tuple or None): La deuxième liste.
    Returns:
        tuple or None: La nouvelle liste concaténée et inversée.
    """
    if est_vide(l1):
        return l2 # Si l1 est vide, son inverse est vide, donc on renvoie juste l2
    else:
        # On prend la tête de l1, et on l'ajoute à la fin de la concaténation
        # inverse de la queue de l1 avec l2
        # C'est magique : en "déroulant" l1, on la reconstruit à l'envers sur l2 !
        return concatener_inverse(l1[1], construire_liste(l1[0], l2))

def renverser_efficace(lst):
    """
    Renvoie une nouvelle liste contenant les éléments de lst dans l'ordre inverse,
    en utilisant concatener_inverse pour une bonne efficacité.
    Args:
        lst (tuple or None): La liste à inverser.
    Returns:
        tuple or None: La liste inversée.
    """
    return concatener_inverse(lst, vide())

# --- Tests ---
print("Exercice 6 :")
L_test1 = construire_liste(1, construire_liste(2, construire_liste(3, vide())))
L_test2 = construire_liste('A', construire_liste('B', vide()))

print(f"Liste 1 : {afficher_liste_simple(L_test1)}") # Attend (1 2 3)
print(f"Liste 2 : {afficher_liste_simple(L_test2)}") # Attend (A B)

# L1 inversée (3 2 1) + L2 (A B) => (3 2 1 A B)
res_concat_inv = concatener_inverse(L_test1, L_test2)
print(f"concatener_inverse(L1, L2) : {afficher_liste_simple(res_concat_inv)}")
# Attend : (3 2 1 A B)

res_renverser = renverser_efficace(L_test1)
print(f"renverser_efficace(L1) : {afficher_liste_simple(res_renverser)}")
# Attend : (3 2 1)

res_renverser_vide = renverser_efficace(vide())
print(f"renverser_efficace(liste_vide) : {afficher_liste_simple(res_renverser_vide)}")
# Attend : ()
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# --- Fonctions à écrire pour l'exercice ---

# Version récursive
def sont_identiques_rec(l1, l2):
    """
    Vérifie récursivement si deux listes (TAD) sont identiques.
    Args:
        l1 (tuple or None): La première liste.
        l2 (tuple or None): La deuxième liste.
    Returns:
        bool: True si les listes sont identiques, False sinon.
    """
    if est_vide(l1) and est_vide(l2):
        return True # Si les deux sont vides, elles sont identiques
    
    if est_vide(l1) or est_vide(l2):
        return False # Si l'une est vide et l'autre non, elles ne sont pas identiques
    
    # Si les têtes sont différentes, les listes ne sont pas identiques
    if l1[0] != l2[0]:
        return False
    
    # Si les têtes sont identiques, on compare récursivement les queues
    return sont_identiques_rec(l1[1], l2[1])

# Version itérative (avec boucle while)
def sont_identiques_iter(l1, l2):
    """
    Vérifie itérativement si deux listes (TAD) sont identiques.
    Args:
        l1 (tuple or None): La première liste.
        l2 (tuple or None): La deuxième liste.
    Returns:
        bool: True si les listes sont identiques, False sinon.
    """
    current_l1 = l1
    current_l2 = l2

    while not est_vide(current_l1) and not est_vide(current_l2):
        if current_l1[0] != current_l2[0]:
            return False # Éléments différents, donc pas identiques
        current_l1 = current_l1[1]
        current_l2 = current_l2[1]
    
    # Après la boucle, les deux listes devraient être vides si elles sont identiques
    return est_vide(current_l1) and est_vide(current_l2)

# --- Tests ---
print("Exercice 7 :")
L_test1 = construire_liste(1, construire_liste(2, construire_liste(3, vide())))
L_test2 = construire_liste(1, construire_liste(2, construire_liste(3, vide())))
L_test3 = construire_liste(1, construire_liste(2, construire_liste(4, vide()))) # Différent par élément
L_test4 = construire_liste(1, construire_liste(2, vide())) # Différent par taille

print(f"L1 : {afficher_liste_simple(L_test1)}")
print(f"L2 : {afficher_liste_simple(L_test2)}")
print(f"L3 : {afficher_liste_simple(L_test3)}")
print(f"L4 : {afficher_liste_simple(L_test4)}")

print(f"L1 et L2 (rec) : {sont_identiques_rec(L_test1, L_test2)}") # Attend True
print(f"L1 et L3 (rec) : {sont_identiques_rec(L_test1, L_test3)}") # Attend False
print(f"L1 et L4 (rec) : {sont_identiques_rec(L_test1, L_test4)}") # Attend False
print(f"L1 et L1 (rec) : {sont_identiques_rec(L_test1, L_test1)}") # Attend True (même référence)
print(f"Liste vide et liste vide (rec) : {sont_identiques_rec(vide(), vide())}") # Attend True
print(f"L1 et liste vide (rec) : {sont_identiques_rec(L_test1, vide())}") # Attend False

print(f"L1 et L2 (iter) : {sont_identiques_iter(L_test1, L_test2)}") # Attend True
print(f"L1 et L3 (iter) : {sont_identiques_iter(L_test1, L_test3)}") # Attend False
print(f"L1 et L4 (iter) : {sont_identiques_iter(L_test1, L_test4)}") # Attend False
print(f"Liste vide et liste vide (iter) : {sont_identiques_iter(vide(), vide())}") # Attend True
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonction à écrire pour l'exercice ---

def inserer_triee(x, lst):
    """
    Insère un élément x dans une liste triée (TAD) en conservant l'ordre.
    Renvoie une nouvelle liste.
    Args:
        x (int): L'entier à insérer.
        lst (tuple or None): La liste d'entiers triée.
    Returns:
        tuple or None: La nouvelle liste avec x inséré.
    """
    if est_vide(lst):
        # Si la liste est vide, on crée une liste avec juste x
        return construire_liste(x, vide())
    
    # Si x est plus petit ou égal à la tête de la liste, x est inséré ici
    if x <= lst[0]:
        return construire_liste(x, lst)
    else:
        # Sinon, x est plus grand que la tête, on cherche sa place dans la queue
        # et on reconstruit la liste avec la tête actuelle.
        return construire_liste(lst[0], inserer_triee(x, lst[1]))

# --- Tests ---
print("Exercice 8 :")
L_triee1 = construire_liste(1, construire_liste(2, construire_liste(5, construire_liste(8, vide()))))
print(f"Liste triée originale : {afficher_liste_simple(L_triee1)}")

res1 = inserer_triee(3, L_triee1)
print(f"Insertion de 3 : {afficher_liste_simple(res1)}") # Attend (1 2 3 5 8)

res2 = inserer_triee(0, L_triee1)
print(f"Insertion de 0 : {afficher_liste_simple(res2)}") # Attend (0 1 2 5 8)

res3 = inserer_triee(10, L_triee1)
print(f"Insertion de 10 : {afficher_liste_simple(res3)}") # Attend (1 2 5 8 10)

res4 = inserer_triee(5, L_triee1) # Insertion d'un doublon
print(f"Insertion de 5 : {afficher_liste_simple(res4)}") # Attend (1 2 5 5 8)

res5 = inserer_triee(7, vide())
print(f"Insertion dans liste vide : {afficher_liste_simple(res5)}") # Attend (7)
print("-" * 20)

# On réutilise les fonctions d'aide et inserer_triee
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonction de l'exercice 8
def inserer_triee(x, lst):
    if est_vide(lst):
        return construire_liste(x, vide())
    if x <= lst[0]:
        return construire_liste(x, lst)
    else:
        return construire_liste(lst[0], inserer_triee(x, lst[1]))

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonction à écrire pour l'exercice ---

def tri_par_insertion(lst):
    """
    Trie une liste (TAD) par insertion récursive.
    Renvoie une nouvelle liste triée.
    Args:
        lst (tuple or None): La liste à trier.
    Returns:
        tuple or None: La nouvelle liste triée.
    """
    if est_vide(lst):
        return vide() # Une liste vide est déjà triée
    
    # On prend la tête de la liste
    tête = lst[0]
    # On trie récursivement la queue de la liste
    queue_triee = tri_par_insertion(lst[1])
    # Et on insère la tête dans la queue triée
    return inserer_triee(tête, queue_triee)

# --- Tests ---
print("Exercice 9 :")
L_non_triee1 = construire_liste(5, construire_liste(2, construire_liste(8, construire_liste(1, construire_liste(3, vide())))))
print(f"Liste non triée : {afficher_liste_simple(L_non_triee1)}")

res_tri1 = tri_par_insertion(L_non_triee1)
print(f"Liste triée : {afficher_liste_simple(res_tri1)}") # Attend (1 2 3 5 8)

L_non_triee2 = construire_liste(9, construire_liste(1, construire_liste(5, vide())))
print(f"Liste non triée : {afficher_liste_simple(L_non_triee2)}")
res_tri2 = tri_par_insertion(L_non_triee2)
print(f"Liste triée : {afficher_liste_simple(res_tri2)}") # Attend (1 5 9)

res_tri_vide = tri_par_insertion(vide())
print(f"Liste vide triée : {afficher_liste_simple(res_tri_vide)}") # Attend ()

L_single = construire_liste(42, vide())
print(f"Liste à un élément triée : {afficher_liste_simple(L_single)}")
res_single = tri_par_insertion(L_single)
print(f"Résultat : {afficher_liste_simple(res_single)}") # Attend (42)
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonction à écrire pour l'exercice ---

# Version itérative (la plus commune et souvent la plus efficace ici)
def tableau_vers_liste_chaine(tableau):
    """
    Convertit un tableau Python en une liste chaînée (TAD).
    Args:
        tableau (list): Le tableau Python.
    Returns:
        tuple or None: La liste chaînée correspondante.
    """
    resultat_liste = vide()
    # On parcourt le tableau EN REVERS pour pouvoir utiliser construire_liste (ajouter en tête)
    for element in reversed(tableau):
        resultat_liste = construire_liste(element, resultat_liste)
    return resultat_liste

# Une version alternative itérative sans reversed (un peu plus complexe car nécessite de gérer le "suivant")
# def tableau_vers_liste_chaine_alt(tableau):
#     if not tableau:
#         return vide()
#     
#     head_node = construire_liste(tableau[0], vide())
#     current_node = head_node
#     
#     for i in range(1, len(tableau)):
#         # Ici, on devrait créer un nouveau nœud et l'attacher à current_node[1]
#         # Mais avec notre implémentation de tuple, c'est pas direct car les tuples sont immuables.
#         # Cette approche serait plus naturelle avec une implémentation de liste chaînée mutable (avec des classes).
#         pass # C'est pourquoi la version reversed est privilégiée ici.


# Version récursive (moins intuitive pour cette tâche)
def tableau_vers_liste_chaine_rec(tableau):
    """
    Convertit récursivement un tableau Python en une liste chaînée (TAD).
    Args:
        tableau (list): Le tableau Python.
    Returns:
        tuple or None: La liste chaînée correspondante.
    """
    if not tableau:
        return vide()
    # On prend le premier élément du tableau et on le construit sur le reste
    # qui est la conversion récursive du reste du tableau.
    return construire_liste(tableau[0], tableau_vers_liste_chaine_rec(tableau[1:]))


# --- Tests ---
print("Exercice 10 :")
tab1 = [10, 20, 30, 40]
res_liste1 = tableau_vers_liste_chaine(tab1)
print(f"Tableau {tab1} -> Liste Chaînée : {afficher_liste_simple(res_liste1)}") # Attend (10 20 30 40)

tab2 = ['a', 'b']
res_liste2 = tableau_vers_liste_chaine(tab2)
print(f"Tableau {tab2} -> Liste Chaînée : {afficher_liste_simple(res_liste2)}") # Attend (a b)

tab3 = []
res_liste3 = tableau_vers_liste_chaine(tab3)
print(f"Tableau {tab3} -> Liste Chaînée : {afficher_liste_simple(res_liste3)}") # Attend ()

print("--- Version Récursive ---")
res_liste1_rec = tableau_vers_liste_chaine_rec(tab1)
print(f"Tableau {tab1} -> Liste Chaînée (réc) : {afficher_liste_simple(res_liste1_rec)}")

res_liste3_rec = tableau_vers_liste_chaine_rec(tab3)
print(f"Tableau {tab3} -> Liste Chaînée (réc) : {afficher_liste_simple(res_liste3_rec)}")
print("-" * 20)

# On réutilise notre implémentation de liste basée sur des tuples
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonction à écrire pour l'exercice ---

def obtenir_derniere_cellule(lst):
    """
    Renvoie la dernière cellule (tuple) d'une liste chaînée non vide.
    Args:
        lst (tuple): La liste chaînée (non vide).
    Returns:
        tuple: La dernière cellule de la liste.
    """
    if est_vide(lst):
        # Cette condition ne devrait normalement pas être atteinte d'après l'énoncé,
        # mais c'est une bonne pratique de la gérer.
        raise ValueError("La liste ne doit pas être vide pour cette opération.")

    current_cell = lst
    # On parcourt tant que la "queue" de la cellule actuelle n'est pas vide (None)
    while not est_vide(current_cell[1]):
        current_cell = current_cell[1] # On passe à la cellule suivante
    return current_cell # Quand la boucle s'arrête, current_cell est la dernière

# --- Tests ---
print("Exercice 11 :")
L_test = construire_liste(1, construire_liste(2, construire_liste(3, vide())))
print(f"Liste de test : {afficher_liste_simple(L_test)}")

derniere = obtenir_derniere_cellule(L_test)
print(f"Dernière cellule de (1 2 3) : {derniere}") # Attend (3, None)

L_single = construire_liste(42, vide())
print(f"Liste à un élément : {afficher_liste_simple(L_single)}")
derniere_single = obtenir_derniere_cellule(L_single)
print(f"Dernière cellule de (42) : {derniere_single}") # Attend (42, None)

# Test du cas d'erreur (si l'énoncé n'avait pas garanti non vide)
try:
    obtenir_derniere_cellule(vide())
except ValueError as e:
    print(f"Erreur attendue sur liste vide : {e}")
print("-" * 20)

# On réutilise nos fonctions d'aide
def vide():
    return None

def construire_liste(x, L):
    return (x, L)

def est_vide(L):
    return L is None

# Fonction de l'exercice 11
def obtenir_derniere_cellule(lst):
    if est_vide(lst):
        raise ValueError("La liste ne doit pas être vide pour cette opération.")
    current_cell = lst
    while not est_vide(current_cell[1]):
        current_cell = current_cell[1]
    return current_cell

# Fonctions d'affichage pour les tests
def afficher_liste_simple(ma_liste):
    elements = []
    current = ma_liste
    while not est_vide(current):
        elements.append(str(current[0]))
        current = current[1]
    return "(" + " ".join(elements) + ")"

# --- Fonction à écrire pour l'exercice (Simulation "en place" par reconstruction) ---

# Fonction auxiliaire pour copier une liste jusqu'à un certain point
def _copier_jusqu_a_element(liste, element_cible, nouvelle_fin):
    """
    Copie la liste 'liste' jusqu'à l'élément 'element_cible' et attache 'nouvelle_fin' à ce point.
    Cette fonction est récursive et gère la reconstruction de la liste IMMUABLE.
    """
    if est_vide(liste):
        # Ne devrait pas arriver si element_cible est dans la liste
        return vide()
    
    # Si on arrive à l'élément cible (la dernière cellule de l1), on change son pointeur
    if liste == element_cible: # Comparaison par identité (même tuple)
        return construire_liste(liste[0], nouvelle_fin)
    
    # Sinon, on copie la tête et on continue la récursion sur la queue
    return construire_liste(liste[0], _copier_jusqu_a_element(liste[1], element_cible, nouvelle_fin))


def concatener_en_place_simule(l1, l2):
    """
    Simule une concaténation "en place" de l1 et l2 pour des listes immuables.
    Args:
        l1 (tuple or None): La première liste.
        l2 (tuple or None): La deuxième liste.
    Returns:
        tuple or None: La nouvelle liste résultante (début de l1 ou l2).
    """
    if est_vide(l1):
        return l2 # Si l1 est vide, le résultat est simplement l2
    
    if est_vide(l2):
        return l1 # Si l2 est vide, le résultat est simplement l1

    # On trouve la dernière "cellule" de l1
    derniere_cell_l1 = obtenir_derniere_cellule(l1)
    
    # Avec des listes immuables (tuples), on ne peut pas faire :
    # derniere_cell_l1[1] = l2 (ça ne marcherait pas car les tuples ne sont pas mutables)
    
    # On doit donc reconstruire l1 en changeant le pointeur de sa dernière cellule.
    # C'est ici que l'approche "en place" perd de son sens avec des immuables.
    # On va reconstruire l1 jusqu'à la dernière cellule, puis la faire pointer vers l2.
    
    # Utilisons la fonction auxiliaire pour "reconstruire" l1 avec le nouveau lien
    # C'est une "modification" qui crée une nouvelle version de l1
    nouvelle_l1 = _copier_jusqu_a_element(l1, derniere_cell_l1, l2)
    
    return nouvelle_l1 # Le début de la concaténation est le début de la nouvelle l1

# --- Tests ---
print("Exercice 12 :")
L_a = construire_liste(1, construire_liste(2, vide()))
L_b = construire_liste('A', construire_liste('B', vide()))

print(f"L_a originale : {afficher_liste_simple(L_a)}")
print(f"L_b originale : {afficher_liste_simple(L_b)}")

# Tentative de concaténation "en place"
L_concat = concatener_en_place_simule(L_a, L_b)

print(f"L_a après simulation : {afficher_liste_simple(L_a)}") # L_a devrait rester inchangée si l'implémentation est immuable
print(f"L_concat (résultat) : {afficher_liste_simple(L_concat)}") # Attend (1 2 A B)

# Test avec L_a vide
L_vide = vide()
L_concat_vide_debut = concatener_en_place_simule(L_vide, L_b)
print(f"L_concat (vide + L_b) : {afficher_liste_simple(L_concat_vide_debut)}") # Attend (A B)

# Test avec L_b vide
L_concat_vide_fin = concatener_en_place_simule(L_a, L_vide)
print(f"L_concat (L_a + vide) : {afficher_liste_simple(L_concat_vide_fin)}") # Attend (1 2)

# Test avec les deux vides
L_concat_deux_vides = concatener_en_place_simule(L_vide, L_vide)
print(f"L_concat (vide + vide) : {afficher_liste_simple(L_concat_deux_vides)}") # Attend ()
print("-" * 20)

class Cellule:
    """une cellule d’une liste chaînée"""
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    """structure de pile"""
    def __init__(self):
        self.contenu = None

    def est_vide(self):
        return self.contenu is None

    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v

def creer_pile():
    return Pile()

class Cellule:
    """une cellule d’une liste chaînée"""
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    """structure de pile"""
    def __init__(self):
        self.contenu = None

    def est_vide(self):
        return self.contenu is None

    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    
    # --- Nouvelles méthodes à compléter ---

    def consulter(self):
        """
        Renvoie l'élément au sommet de la pile sans le retirer.
        Lève une IndexError si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur # On accède juste à la valeur de la cellule de tête

    def vider(self):
        """
        Vide complètement la pile.
        """
        self.contenu = None # La magie opère : il suffit de "lâcher" la référence à la première cellule !
                           # Le ramasse-miettes de Python fera le reste.

    def taille(self):
        """
        Renvoie le nombre d'éléments dans la pile.
        """
        compteur = 0
        courant = self.contenu # On part de la première cellule
        while courant is not None:
            compteur += 1
            courant = courant.suivante # On avance à la cellule suivante
        return compteur

def creer_pile():
    return Pile()

# --- Tests ---
print("Exercice 13 : Compléter la Classe Pile")
ma_pile = creer_pile()
print(f"Pile est vide ? {ma_pile.est_vide()}") # Attend True
ma_pile.empiler(10)
ma_pile.empiler(20)
ma_pile.empiler(30)
print(f"Pile après empilement : {ma_pile.consulter()} au sommet") # Attend 30
print(f"Taille de la pile : {ma_pile.taille()}") # Attend 3
print(f"Élément consulté : {ma_pile.consulter()}") # Attend 30 (et la pile n'est pas modifiée)
print(f"Élément dépilé : {ma_pile.depiler()}") # Attend 30
print(f"Pile après dépilement : {ma_pile.consulter()} au sommet") # Attend 20
print(f"Taille de la pile : {ma_pile.taille()}") # Attend 2

ma_pile.vider()
print(f"Pile est vide après vider ? {ma_pile.est_vide()}") # Attend True
print(f"Taille de la pile après vider : {ma_pile.taille()}") # Attend 0

# Test d'erreur pour consulter et depiler sur pile vide
try:
    ma_pile.consulter()
except IndexError as e:
    print(f"Erreur attendue : {e}")

try:
    ma_pile.depiler()
except IndexError as e:
    print(f"Erreur attendue : {e}")
print("-" * 20)

class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    # ... (code de la classe Pile de l'exercice 13, y compris est_vide, empiler, depiler)
    # Pour cet exercice, nous aurons besoin de consulter() et est_vide()
    def __init__(self):
        self.contenu = None
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    def consulter(self): # Ajoutée pour cet exercice
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur


adresse_courante = ""
adresses_precedentes = Pile()

def aller_a(adresse_cible):
    global adresse_courante
    global adresses_suivantes # On anticipe l'ajout de cette pile
    
    if adresse_courante: # N'empile que si on vient d'une page existante
        adresses_precedentes.empiler(adresse_courante)
    adresse_courante = adresse_cible
    adresses_suivantes.vider() # Toute nouvelle navigation annule l'historique "avant"

def retour():
    global adresse_courante
    global adresses_suivantes # On en aura besoin ici

    if not adresses_precedentes.est_vide():
        # Avant de partir de l'adresse courante, on l'empile dans adresses_suivantes
        if adresse_courante: # S'il y a une adresse courante à enregistrer
            adresses_suivantes.empiler(adresse_courante)
        adresse_courante = adresses_precedentes.depiler()
    else:
        print("Plus d'adresses précédentes. Impossible de revenir plus loin.")
        # On pourrait choisir de ne rien faire ou de vider adresse_courante si on veut
        # adresse_courante = "" # Optionnel : vider l'adresse courante si on est au début

class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    def __init__(self):
        self.contenu = None
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    def consulter(self):
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur
    def vider(self): # On a besoin de vider pour cet exercice
        self.contenu = None

# --- Variables globales du simulateur de navigateur ---
adresse_courante = ""
adresses_precedentes = Pile()
adresses_suivantes = Pile() # La nouvelle pile pour l'historique "retour avant"

def aller_a(adresse_cible):
    """
    Simule la navigation vers une nouvelle adresse.
    Empile l'adresse courante dans les adresses précédentes et vide les adresses suivantes.
    """
    global adresse_courante
    global adresses_precedentes
    global adresses_suivantes
    
    if adresse_courante: # N'empile que si on vient d'une page existante (pas le premier aller_a)
        adresses_precedentes.empiler(adresse_courante)
    
    adresse_courante = adresse_cible
    adresses_suivantes.vider() # Toute nouvelle navigation annule l'historique "retour avant"
    print(f"-> Navigué vers : {adresse_courante}")

def retour():
    """
    Revient à l'adresse précédente.
    Place la page actuelle dans adresses_suivantes avant de revenir.
    """
    global adresse_courante
    global adresses_precedentes
    global adresses_suivantes

    if not adresses_precedentes.est_vide():
        # Avant de changer l'adresse courante, on l'empile pour pouvoir y revenir avec retour_avant
        if adresse_courante: # S'il y a bien une page courante à quitter
            adresses_suivantes.empiler(adresse_courante)
        
        adresse_courante = adresses_precedentes.depiler()
        print(f"<- Retour vers : {adresse_courante}")
    else:
        print("Oh non, tu es arrivé au début de l'histoire ! Plus de pages précédentes.")

def retour_avant():
    """
    Avance vers une adresse précédemment "retournée" (annule un retour).
    Place la page actuelle dans adresses_precedentes avant d'avancer.
    """
    global adresse_courante
    global adresses_precedentes
    global adresses_suivantes

    if not adresses_suivantes.est_vide():
        # Avant de changer l'adresse courante, on l'empile dans adresses_precedentes
        # pour pouvoir revenir à cette page si on refait un "retour" classique
        if adresse_courante:
            adresses_precedentes.empiler(adresse_courante)
        
        adresse_courante = adresses_suivantes.depiler()
        print(f"->-> Retour avant vers : {adresse_courante}")
    else:
        print("Tu es déjà à la fin de ton futur proche ! Plus de pages 'retour avant'.")

# --- Tests de la simulation ---
print("Exercice 14 : Navigateur Web avec Historique 'Retour Avant'")
print("--- Début de la navigation ---")
aller_a("google.com")
aller_a("github.com")
aller_a("youtube.com")
aller_a("stack_overflow.com")

print(f"\nPage actuelle : {adresse_courante}") # stack_overflow.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # youtube.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # vide

print("\n--- On revient en arrière ---")
retour() # Retourne à youtube.com
print(f"Page actuelle : {adresse_courante}") # youtube.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # github.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # stack_overflow.com

retour() # Retourne à github.com
print(f"Page actuelle : {adresse_courante}") # github.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # google.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # youtube.com (en dessous) / stack_overflow.com (au dessus)

print("\n--- On fait un 'retour avant' ---")
retour_avant() # Avance à youtube.com
print(f"Page actuelle : {adresse_courante}") # youtube.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # github.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # stack_overflow.com

retour_avant() # Avance à stack_overflow.com
print(f"Page actuelle : {adresse_courante}") # stack_overflow.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # youtube.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # vide

print("\n--- On navigue à nouveau, cela vide l'historique 'retour avant' ---")
aller_a("new_website.com")
print(f"Page actuelle : {adresse_courante}") # new_website.com
print(f"Précédentes (sommet) : {adresses_precedentes.consulter() if not adresses_precedentes.est_vide() else 'vide'}") # stack_overflow.com
print(f"Suivantes (sommet) : {adresses_suivantes.consulter() if not adresses_suivantes.est_vide() else 'vide'}") # vide (vidé !)

print("\n--- Tentative de retour avant quand pile vide ---")
retour_avant() # Devrait dire "Plus de pages 'retour avant'."
print("-" * 20)

class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    """structure de pile avec taille optimisée"""
    def __init__(self):
        self.contenu = None
        self._taille = 0 # NOUVEL ATTRIBUT : on initialise la taille à 0

    def est_vide(self):
        return self.contenu is None
        # Ou alternativement : return self._taille == 0

    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
        self._taille += 1 # MODIFICATION : on incrémente la taille à chaque empilement

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        self._taille -= 1 # MODIFICATION : on décrémente la taille à chaque dépilement
        return v
    
    # Méthodes additionnelles de l'exercice 13
    def consulter(self):
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur

    def vider(self):
        self.contenu = None
        self._taille = 0 # MODIFICATION : la taille redevient 0 quand on vide

    def taille(self):
        """
        Renvoie le nombre d'éléments dans la pile (maintenant en O(1)).
        """
        return self._taille # MODIFICATION : On renvoie directement l'attribut, c'est instantané !

def creer_pile():
    return Pile()

# --- Tests ---
print("Exercice 15 : Pile Optimisée avec Attribut _taille")
ma_pile_opti = creer_pile()
print(f"Taille initiale : {ma_pile_opti.taille()}") # Attend 0
ma_pile_opti.empiler("pomme")
ma_pile_opti.empiler("banane")
print(f"Taille après 2 empilements : {ma_pile_opti.taille()}") # Attend 2
ma_pile_opti.depiler()
print(f"Taille après 1 dépilement : {ma_pile_opti.taille()}") # Attend 1
ma_pile_opti.vider()
print(f"Taille après vider : {ma_pile_opti.taille()}") # Attend 0
ma_pile_opti.empiler("cerise")
print(f"Taille après nouvel empilement : {ma_pile_opti.taille()}") # Attend 1
print("-" * 20)

# Réutilisation de la classe Pile (avec optimisation de taille, mais pas obligatoire ici)
class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    def __init__(self):
        self.contenu = None
        self._taille = 0 # Pour cet exercice, la taille est utile pour les vérifs
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
        self._taille += 1
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        self._taille -= 1
        return v
    def taille(self): # On a besoin de la taille pour les vérifs d'erreur
        return self._taille

def creer_pile():
    return Pile()

# --- Fonction à écrire pour l'exercice ---

def calculer_rpn(expression_rpn_str):
    """
    Calcule la valeur d'une expression en notation polonaise inverse (RPN).
    Gère les opérateurs '+' et '*'.
    Args:
        expression_rpn_str (str): La chaîne de caractères représentant l'expression RPN.
    Returns:
        int: La valeur calculée de l'expression.
    Raises:
        ValueError: Si l'expression est mal formée (pas assez d'opérandes, etc.).
    """
    pile_calcul = creer_pile()
    elements = expression_rpn_str.split() # Sépare la chaîne en une liste d'éléments (nombres ou opérateurs)

    for element in elements:
        try:
            # Tente de convertir l'élément en entier (c'est un nombre)
            nombre = int(element)
            pile_calcul.empiler(nombre)
        except ValueError:
            # Si ce n'est pas un nombre, c'est un opérateur
            if element == '+':
                if pile_calcul.taille() < 2:
                    raise ValueError("Erreur RPN : pas assez d'opérandes pour l'addition.")
                op2 = pile_calcul.depiler() # Le premier dépilé est le deuxième opérande
                op1 = pile_calcul.depiler() # Le deuxième dépilé est le premier opérande
                resultat = op1 + op2
                pile_calcul.empiler(resultat)
            elif element == '*':
                if pile_calcul.taille() < 2:
                    raise ValueError("Erreur RPN : pas assez d'opérandes pour la multiplication.")
                op2 = pile_calcul.depiler()
                op1 = pile_calcul.depiler()
                resultat = op1 * op2
                pile_calcul.empiler(resultat)
            else:
                raise ValueError(f"Erreur RPN : Opérateur inconnu '{element}'.")

    # À la fin, la pile doit contenir exactement un élément : le résultat
    if pile_calcul.taille() != 1:
        raise ValueError("Erreur RPN : Expression mal formée ou incomplète (reste trop ou pas assez d'éléments).")
    
    return pile_calcul.depiler() # Le résultat est le seul élément restant

# --- Tests ---
print("Exercice 16 : Calculatrice Polonaise Inverse (RPN)")

# Test 1 : L'exemple de l'énoncé
expression1 = '1 2 3 * + 4 *' # (1 + 2 * 3) * 4 = (1 + 6) * 4 = 7 * 4 = 28
print(f"Expression : '{expression1}' -> Résultat : {calculer_rpn(expression1)}") # Attend 28

# Test 2 : Une expression plus simple
expression2 = '5 2 +' # 5 + 2 = 7
print(f"Expression : '{expression2}' -> Résultat : {calculer_rpn(expression2)}") # Attend 7

# Test 3 : Une autre multiplication
expression3 = '10 3 *' # 10 * 3 = 30
print(f"Expression : '{expression3}' -> Résultat : {calculer_rpn(expression3)}") # Attend 30

# Test 4 : Une expression avec plusieurs opérations
expression4 = '7 2 + 3 *' # (7 + 2) * 3 = 9 * 3 = 27
print(f"Expression : '{expression4}' -> Résultat : {calculer_rpn(expression4)}") # Attend 27

# Test 5 : Expression mal formée (pas assez d'opérandes)
expression_mal_formee1 = '5 +'
try:
    print(f"Expression : '{expression_mal_formee1}' -> Résultat : {calculer_rpn(expression_mal_formee1)}")
except ValueError as e:
    print(f"Erreur attendue : {e}")

# Test 6 : Expression mal formée (trop d'opérandes à la fin)
expression_mal_formee2 = '1 2 3 +'
try:
    print(f"Expression : '{expression_mal_formee2}' -> Résultat : {calculer_rpn(expression_mal_formee2)}")
except ValueError as e:
    print(f"Erreur attendue : {e}")

# Test 7 : Opérateur inconnu
expression_mal_formee3 = '1 2 %'
try:
    print(f"Expression : '{expression_mal_formee3}' -> Résultat : {calculer_rpn(expression_mal_formee3)}")
except ValueError as e:
    print(f"Erreur attendue : {e}")

# Test 8 : Expression vide
expression_vide = ''
try:
    print(f"Expression : '{expression_vide}' -> Résultat : {calculer_rpn(expression_vide)}")
except ValueError as e:
    print(f"Erreur attendue : {e}") # Attend Erreur RPN : Expression mal formée ou incomplète (reste trop ou pas assez d'éléments).
print("-" * 20)

# Réutilisation de la classe Pile
class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    def __init__(self):
        self.contenu = None
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    def consulter(self):
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur

def creer_pile():
    return Pile()

# --- Fonction à écrire pour l'exercice ---

def trouver_parenthèse_ouvrante_associée(chaine, indice_fermante):
    """
    Trouve l'indice de la parenthèse ouvrante associée à une parenthèse fermante.
    La chaîne est supposée bien parenthésée.
    Args:
        chaine (str): La chaîne de caractères.
        indice_fermante (int): L'indice de la parenthèse fermante ')'.
    Returns:
        int: L'indice de la parenthèse ouvrante '('.
    Raises:
        ValueError: Si indice_fermante ne pointe pas sur une parenthèse fermante
                    ou si la chaîne n'est pas bien parenthésée (cas non géré par l'énoncé,
                    mais bonne pratique de sécurité).
    """
    if chaine[indice_fermante] != ')':
        raise ValueError("L'indice donné ne pointe pas sur une parenthèse fermante.")
    
    pile_indices_ouvrantes = creer_pile()
    
    # On parcourt la chaîne depuis le début jusqu'à l'indice de la parenthèse fermante
    for i in range(indice_fermante):
        caractere = chaine[i]
        
        if caractere == '(':
            pile_indices_ouvrantes.empiler(i) # On empile l'indice de chaque parenthèse ouvrante
        elif caractere == ')':
            # Si on rencontre une parenthèse fermante, elle ferme la dernière ouvrante non fermée.
            # Donc, on dépile l'indice de cette ouvrante, car elle est maintenant "fermée".
            if pile_indices_ouvrantes.est_vide():
                raise ValueError("Chaîne mal parenthésée : parenthèse fermante sans ouvrante correspondante.")
            pile_indices_ouvrantes.depiler()
            
    # Quand on arrive à l'indice_fermante, le sommet de la pile doit être l'indice de son ouvrante associée
    if pile_indices_ouvrantes.est_vide():
        raise ValueError("Chaîne mal parenthésée : parenthèse fermante sans ouvrante correspondante (problème d'indice).")
    
    return pile_indices_ouvrantes.depiler() # Le sommet est l'indice recherché !

# --- Tests ---
print("Exercice 17 : Parenthèse Associée (Trouver l'Ouvrante)")

chaine1 = "((A+B)*(C-D))"
# Indices :      0123456789012
# Caractères :   ((A+B)*(C-D))
# indice_fermante : 6 (pour le premier ')'), 12 (pour le dernier ')')

print(f"Chaîne : '{chaine1}'")
print(f"Indice fermante 6 (')') : ouvrante à l'indice {trouver_parenthèse_ouvrante_associée(chaine1, 6)}") # Attend 2
print(f"Indice fermante 12 (')') : ouvrante à l'indice {trouver_parenthèse_ouvrante_associée(chaine1, 12)}") # Attend 0

chaine2 = "(X(Y)Z)"
# Indices :      0123456
# Caractères :   (X(Y)Z)
print(f"\nChaîne : '{chaine2}'")
print(f"Indice fermante 4 (')') : ouvrante à l'indice {trouver_parenthèse_ouvrante_associée(chaine2, 4)}") # Attend 2
print(f"Indice fermante 6 (')') : ouvrante à l'indice {trouver_parenthèse_ouvrante_associée(chaine2, 6)}") # Attend 0

# Test avec une chaîne simple
chaine3 = "(coucou)"
print(f"\nChaîne : '{chaine3}'")
print(f"Indice fermante 7 (')') : ouvrante à l'indice {trouver_parenthèse_ouvrante_associée(chaine3, 7)}") # Attend 0

# Test d'erreur (si l'énoncé n'avait pas supposé "bien parenthésée")
try:
    chaine_mal_formee = "())("
    trouver_parenthèse_ouvrante_associée(chaine_mal_formee, 2)
except ValueError as e:
    print(f"\nErreur attendue : {e}") # Chaîne mal parenthésée : parenthèse fermante sans ouvrante correspondante.
print("-" * 20)

# Réutilisation de la classe Pile
class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    def __init__(self):
        self.contenu = None
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    def consulter(self):
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.contenu.valeur
    def taille(self): # Utile pour la vérif finale
        compteur = 0
        courant = self.contenu
        while courant is not None:
            compteur += 1
            courant = courant.suivante
        return compteur

def creer_pile():
    return Pile()

# --- Fonction à écrire pour l'exercice ---

def est_bien_parenthésée(chaine):
    """
    Vérifie si une chaîne de caractères est bien parenthésée avec '(' ')' et '[' ']'.
    Args:
        chaine (str): La chaîne à vérifier.
    Returns:
        bool: True si la chaîne est bien parenthésée, False sinon.
    """
    pile_parenthèses_ouvrantes = creer_pile()
    
    # Dictionnaire pour associer chaque parenthèse fermante à son ouvrante correspondante
    paires_parenthèses = {')': '(', ']': '['}

    for caractere in chaine:
        if caractere in ['(', '[']:
            # Si c'est une parenthèse ouvrante, on l'empile
            pile_parenthèses_ouvrantes.empiler(caractere)
        elif caractere in [')', ']']:
            # Si c'est une parenthèse fermante
            if pile_parenthèses_ouvrantes.est_vide():
                return False # Il y a une parenthèse fermante sans parenthèse ouvrante correspondante
            
            # On dépile la dernière parenthèse ouvrante
            derniere_ouvrante = pile_parenthèses_ouvrantes.depiler()
            
            # On vérifie si la parenthèse ouvrante dépilée correspond à la fermante actuelle
            if paires_parenthèses[caractere] != derniere_ouvrante:
                return False # La forme ne correspond pas (ex: (] )

    # À la fin, la pile doit être vide. Si elle ne l'est pas,
    # il reste des parenthèses ouvrantes non fermées.
    return pile_parenthèses_ouvrantes.est_vide()

# --- Tests ---
print("Exercice 18 : Vérification de Chaînes Bien Parenthésées (Multiples Types)")

print(f"'([])' est bien parenthésée : {est_bien_parenthésée('([])')}") # Attend True
print(f"'([{}])' est bien parenthésée : {est_bien_parenthésée('([{}]')}") # FAUX : l'énoncé n'incluait pas {}, donc False attendu
# Pour le test, je vais m'en tenir à '(' ')' '[' ']'

print(f"'([()])' est bien parenthésée : {est_bien_parenthésée('([()])')}") # Attend True
print(f"'(' est bien parenthésée : {est_bien_parenthésée('(')}") # Attend False (non fermée)
print(f"')' est bien parenthésée : {est_bien_parenthésée(')')}") # Attend False (fermante sans ouvrante)
print(f"'([)]' est bien parenthésée : {est_bien_parenthésée('([)]')}") # Attend False (mismatch de type)
print(f"'[)' est bien parenthésée : {est_bien_parenthésée('[)')}") # Attend False (mismatch de type)
print(f"'' (vide) est bien parenthésée : {est_bien_parenthésée('')}") # Attend True
print(f"'(a[b]c)' est bien parenthésée : {est_bien_parenthésée('(a[b]c)')}") # Attend True (autres caractères ignorés)
print(f"'](' est bien parenthésée : {est_bien_parenthésée('](')}") # Attend False (fermante sans ouvrante)
print("-" * 20)

# Réutilisation de la classe Pile (pour des éléments hétérogènes)
class Cellule:
    def __init__(self, v, s):
        self.valeur = v
        self.suivante = s

class Pile:
    def __init__(self):
        self.contenu = None
    def est_vide(self):
        return self.contenu is None
    def empiler(self, v):
        self.contenu = Cellule(v, self.contenu)
    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        v = self.contenu.valeur
        self.contenu = self.contenu.suivante
        return v
    def consulter(self):
        if self.est_vide():
            return None # Retourne None au lieu de lever une erreur pour faciliter les vérifs
        return self.contenu.valeur
    def taille(self):
        compteur = 0
        courant = self.contenu
        while courant is not None:
            compteur += 1
            courant = courant.suivante
        return compteur


def creer_pile():
    return Pile()

# --- Fonctions à écrire pour l'exercice ---

# Dictionnaire des priorités des opérateurs (plus le nombre est grand, plus la priorité est élevée)
PRIORITES_OPERATEURS = {
    '+': 1,
    '*': 2
}

def appliquer_operateur(op, op1, op2):
    """Applique l'opérateur sur les deux opérandes."""
    if op == '+':
        return op1 + op2
    elif op == '*':
        return op1 * op2
    else:
        raise ValueError(f"Opérateur inconnu : {op}")

def simplifier_operations(pile, operateurs_prioritaires):
    """
    Simplifie les opérations au sommet de la pile si l'opérateur est dans operateurs_prioritaires.
    Continue tant qu'il y a un opérateur pertinent au sommet.
    Args:
        pile (Pile): La pile contenant les éléments de l'expression.
        operateurs_prioritaires (set): Un ensemble d'opérateurs à simplifier.
    Raises:
        ValueError: Si la pile est mal formée pour l'opération.
    """
    while True:
        # On vérifie qu'il y a au moins 3 éléments pour une opération (op1, op, op2)
        if pile.taille() < 3:
            break # Pas assez d'éléments pour une opération
        
        # Le sommet de la pile doit être un nombre (op2)
        op2_val = pile.consulter()
        if not isinstance(op2_val, (int, float)): # On accepte int/float pour les nombres
            break # Le sommet n'est pas un nombre, on ne peut pas simplifier une opération
        pile.depiler() # Dépile op2

        # Le nouvel sommet doit être un opérateur
        operateur = pile.consulter()
        if not isinstance(operateur, str) or operateur not in operateurs_prioritaires:
            pile.empiler(op2_val) # On remet op2 car l'opérateur ne nous intéresse pas
            break # Pas l'opérateur désiré au sommet, ou ce n'est pas une chaîne
        pile.depiler() # Dépile l'opérateur

        # L'avant-dernier élément doit être un nombre (op1)
        op1_val = pile.consulter()
        if not isinstance(op1_val, (int, float)):
            # Oh non, la pile est mal formée ! On remet tout et on lève l'erreur.
            pile.empiler(operateur)
            pile.empiler(op2_val)
            raise ValueError("Pile mal formée : opérande manquant avant un opérateur.")
        pile.depiler() # Dépile op1

        # On applique l'opération et on empile le résultat
        resultat = appliquer_operateur(operateur, op1_val, op2_val)
        pile.empiler(resultat)

def calculer_expression(expression_str):
    """
    Évalue une expression arithmétique avec priorités et parenthèses.
    Args:
        expression_str (str): La chaîne de caractères de l'expression.
    Returns:
        int or float: La valeur de l'expression.
    Raises:
        ValueError: Si l'expression est mal formée.
    """
    pile = creer_pile()
    elements = expression_str.split()

    for element in elements:
        try:
            # Si c'est un nombre, l'empiler
            nombre = int(element)
            pile.empiler(nombre)
        except ValueError:
            # Si ce n'est pas un nombre, c'est un symbole
            if element == '(':
                pile.empiler(element)
            elif element == ')':
                # Simplifier toutes les opérations jusqu'à la parenthèse ouvrante
                simplifier_operations(pile, set(PRIORITES_OPERATEURS.keys())) # Simplifie tous les opérateurs
                
                # Vérifier que le sommet est un nombre et l'avant-dernier une '('
                if pile.est_vide() or not isinstance(pile.consulter(), (int, float)):
                    raise ValueError("Parenthèse fermante inattendue ou expression mal formée (pas de nombre avant ')').")
                
                resultat_parenthèse = pile.depiler() # Le résultat de l'opération entre parenthèses
                
                if pile.est_vide() or pile.depiler() != '(': # L'avant-dernier doit être '(' et on le retire
                    raise ValueError("Parenthèse fermante sans parenthèse ouvrante correspondante.")
                
                pile.empiler(resultat_parenthèse) # Empiler le résultat de la parenthèse
            elif element in PRIORITES_OPERATEURS:
                # Si c'est un opérateur, simplifier les opérateurs de priorité égale ou supérieure
                operateurs_a_simplifier = {op for op, prio in PRIORITES_OPERATEURS.items() 
                                            if prio >= PRIORITES_OPERATEURS[element]}
                simplifier_operations(pile, operateurs_a_simplifier)
                pile.empiler(element) # Empiler le nouvel opérateur
            else:
                raise ValueError(f"Élément inconnu dans l'expression : '{element}'.")
    
    # Après avoir parcouru tous les éléments, simplifier toutes les opérations restantes
    simplifier_operations(pile, set(PRIORITES_OPERATEURS.keys()))

    # À la fin, la pile doit contenir un seul élément : le résultat final
    if pile.taille() != 1 or not isinstance(pile.consulter(), (int, float)):
        raise ValueError("Expression mal formée ou incomplète (reste trop ou pas assez d'éléments, ou pas un nombre final).")
    
    return pile.depiler()

# --- Tests ---
print("Exercice 19 : Calculatrice Ordinaire")

# Exemple de l'énoncé : (1 + 2 * 3) * 4 = (1 + 6) * 4 = 7 * 4 = 28
expr1 = '( 1 + 2 * 3 ) * 4'
print(f"'{expr1}' = {calculer_expression(expr1)}") # Attend 28

# Exemple simple
expr2 = '5 + 2 * 3' # 5 + 6 = 11
print(f"'{expr2}' = {calculer_expression(expr2)}") # Attend 11

# Autre exemple
expr3 = '( 10 - 5 ) * 2' # N'inclut pas le '-' par défaut, donc erreur attendue
try:
    print(f"'{expr3}' = {calculer_expression(expr3)}")
except ValueError as e:
    print(f"Erreur attendue : {e}") # Élément inconnu : '-'

# Pour que ça marche avec -, il faut l'ajouter :
PRIORITES_OPERATEURS['-'] = 1 # Même priorité que +
def appliquer_operateur_full(op, op1, op2):
    if op == '+': return op1 + op2
    elif op == '*': return op1 * op2
    elif op == '-': return op1 - op2
    else: raise ValueError(f"Opérateur inconnu : {op}")
# Et modifier la fonction simplifier_operations pour utiliser cette nouvelle fonction
# Pour rester fidèle à l'exercice original, je n'implémente pas ça ici.

expr4 = '2 * ( 3 + 4 )' # 2 * 7 = 14
print(f"'{expr4}' = {calculer_expression(expr4)}") # Attend 14

expr5 = '1 + 2 + 3 + 4' # 10
print(f"'{expr5}' = {calculer_expression(expr5)}") # Attend 10

expr6 = '( ( 1 + 2 ) * 3 )' # (3 * 3) = 9
print(f"'{expr6}' = {calculer_expression(expr6)}") # Attend 9

# Tests d'erreur
expr_err1 = '1 + * 2'
try:
    print(f"'{expr_err1}' = {calculer_expression(expr_err1)}")
except ValueError as e:
    print(f"Erreur attendue : {e}") # Pile mal formée : opérande manquant...

expr_err2 = '( 1 + 2'
try:
    print(f"'{expr_err2}' = {calculer_expression(expr_err2)}")
except ValueError as e:
    print(f"Erreur attendue : {e}") # Expression mal formée ou incomplète...

expr_err3 = '1 + )'
try:
    print(f"'{expr_err3}' = {calculer_expression(expr_err3)}")
except ValueError as e:
    print(f"Erreur attendue : {e}") # Parenthèse fermante sans parenthèse ouvrante correspondante.
print("-" * 20)

Indices : 0         1         ...      nb-1      nb      ... capacité-1
           |         |         ...       |        |      ...      |
Contenu : [ a ,       b ,       ...      z ,     None ,   ...    None  ]
                                                     ^
                                                     |
                                                (Prochaine case libre)

class PileBornee:
    """Structure de pile bornée implémentée avec un tableau (liste Python)."""
    def __init__(self, capacite):
        if capacite <= 0:
            raise ValueError("La capacité d'une pile bornée doit être positive.")
        self.capacite = capacite
        self.tableau = [None] * capacite # Le tableau fixe de taille 'capacite'
        self.nb_elements = 0 # Indique le nombre d'éléments et l'indice de la prochaine case libre

    def est_vide(self):
        return self.nb_elements == 0

    def est_pleine(self):
        return self.nb_elements == self.capacite

    def empiler(self, e):
        if self.est_pleine():
            raise IndexError("empiler sur une pile pleine")
        
        self.tableau[self.nb_elements] = e # On ajoute l'élément à l'indice de la prochaine case libre
        self.nb_elements += 1 # On incrémente le nombre d'éléments (qui devient le nouvel indice de la case libre)

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        
        self.nb_elements -= 1 # On décrémente le nombre d'éléments pour pointer sur le dernier
        valeur = self.tableau[self.nb_elements] # On récupère l'élément au sommet
        self.tableau[self.nb_elements] = None # Optionnel: "vider" la case (pour le ramasse-miettes)
        return valeur

    def consulter(self): # Utile pour les tests, comme à l'exercice 13
        if self.est_vide():
            raise IndexError("consulter sur une pile vide")
        return self.tableau[self.nb_elements - 1] # Le sommet est le dernier élément ajouté


def creer_pile_bornee(c):
    return PileBornee(c)

# --- Tests ---
print("Exercice 20 : Pile Bornée (Implémentation par Tableau)")
ma_pile_bornee = creer_pile_bornee(3) # Capacité de 3

print(f"Pile vide ? {ma_pile_bornee.est_vide()}") # Attend True
print(f"Pile pleine ? {ma_pile_bornee.est_pleine()}") # Attend False
print(f"Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 0

ma_pile_bornee.empiler("pomme")
print(f"Empilé 'pomme'. Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 1
print(f"Sommet : {ma_pile_bornee.consulter()}") # Attend 'pomme'

ma_pile_bornee.empiler("banane")
print(f"Empilé 'banane'. Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 2
print(f"Sommet : {ma_pile_bornee.consulter()}") # Attend 'banane'

ma_pile_bornee.empiler("cerise")
print(f"Empilé 'cerise'. Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 3
print(f"Sommet : {ma_pile_bornee.consulter()}") # Attend 'cerise'
print(f"Pile pleine ? {ma_pile_bornee.est_pleine()}") # Attend True

# Test d'empilement sur pile pleine
try:
    ma_pile_bornee.empiler("kiwi")
except IndexError as e:
    print(f"Erreur attendue : {e}")

print(f"Dépilé : {ma_pile_bornee.depiler()}") # Attend 'cerise'
print(f"Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 2
print(f"Sommet : {ma_pile_bornee.consulter()}") # Attend 'banane'
print(f"Pile pleine ? {ma_pile_bornee.est_pleine()}") # Attend False

ma_pile_bornee.depiler()
ma_pile_bornee.depiler()
print(f"Nombre d'éléments : {ma_pile_bornee.nb_elements}") # Attend 0
print(f"Pile vide ? {ma_pile_bornee.est_vide()}") # Attend True

# Test de dépilement sur pile vide
try:
    ma_pile_bornee.depiler()
except IndexError as e:
    print(f"Erreur attendue : {e}")
print("-" * 20)

État 1 : File non pleine
Indices : 0           ...         premier      ...   (premier+nb-1)%cap    ... capacité-1
           |                        |                           |
Contenu : [None, ..., None, ...,    a   ,      b    ,   ...     z   ,    None, ..., None]
                                   ^                                      ^
                                   |                                      |
                                 premier                                 (premier+nb)%cap (prochaine place pour ajouter)

État 2 : File circulaire (les éléments "débordent")
Indices : 0           ...   (premier+nb-1)%cap ...   premier-1    premier   ... capacité-1
           |                        |                       |          |
Contenu : [ k ,       l ,   ...     z   ,       None, ..., None,    a   ,      b    , ...   j ]
           ^                                                ^          ^
           |                                                |          |
      (premier+nb)%cap                                    premier    (premier+nb)%cap si vide

class FileBornee:
    """Structure de file bornée implémentée avec un tableau circulaire."""
    def __init__(self, capacite):
        if capacite <= 0:
            raise ValueError("La capacité d'une file bornée doit être positive.")
        self.capacite = capacite
        self.tableau = [None] * capacite # Le tableau fixe
        self.nb_elements = 0 # Nombre d'éléments actuellement dans la file
        self.premier_indice = 0 # Indice du premier élément (tête de la file)
        # L'indice de la prochaine case où ajouter un élément sera :
        # (self.premier_indice + self.nb_elements) % self.capacite

    def est_vide(self):
        return self.nb_elements == 0

    def est_pleine(self):
        return self.nb_elements == self.capacite

    def ajouter(self, e):
        if self.est_pleine():
            raise IndexError("ajouter sur une file pleine")
        
        # Calcul de l'indice où ajouter le nouvel élément
        # C'est (premier_indice + nombre_elements) % capacite
        indice_ajout = (self.premier_indice + self.nb_elements) % self.capacite
        self.tableau[indice_ajout] = e
        self.nb_elements += 1 # Incrémente le nombre d'éléments

    def retirer(self):
        if self.est_vide():
            raise IndexError("retirer d'une file vide")
        
        valeur = self.tableau[self.premier_indice] # Récupère l'élément à la tête
        self.tableau[self.premier_indice] = None # Optionnel: "vider" la case
        
        # Avance l'indice du premier élément de manière circulaire
        self.premier_indice = (self.premier_indice + 1) % self.capacite
        self.nb_elements -= 1 # Décrémente le nombre d'éléments
        return valeur

    def consulter_premier(self): # Méthode ajoutée pour consulter le premier sans le retirer
        if self.est_vide():
            raise IndexError("consulter sur une file vide")
        return self.tableau[self.premier_indice]

def creer_file_bornee(c):
    return FileBornee(c)

# --- Tests ---
print("Exercice 21 : File Bornée (Implémentation par Tableau Circulaire)")
ma_file_bornee = creer_file_bornee(4) # Capacité de 4

print(f"File vide ? {ma_file_bornee.est_vide()}") # True
print(f"File pleine ? {ma_file_bornee.est_pleine()}") # False
print(f"Nombre d'éléments : {ma_file_bornee.nb_elements}") # 0
print(f"Premier indice : {ma_file_bornee.premier_indice}") # 0
print(f"Tableau initial : {ma_file_bornee.tableau}") # [None, None, None, None]

ma_file_bornee.ajouter("Client A")
print(f"\nAjout Client A. Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 1, Premier: 0, Tableau: ['Client A', None, None, None]

ma_file_bornee.ajouter("Client B")
print(f"Ajout Client B. Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 2, Premier: 0, Tableau: ['Client A', 'Client B', None, None]

print(f"\nConsultation premier : {ma_file_bornee.consulter_premier()}") # Attendu: Client A

print(f"Retrait : {ma_file_bornee.retirer()}") # Attendu: Client A
print(f"Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 1, Premier: 1, Tableau: [None, 'Client B', None, None]

ma_file_bornee.ajouter("Client C")
ma_file_bornee.ajouter("Client D")
ma_file_bornee.ajouter("Client E") # La file devrait être pleine après ça

print(f"\nAjouts C, D, E. Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 4, Premier: 1, Tableau: ['Client E', 'Client B', 'Client C', 'Client D']
# 'Client B' à indice 1, 'Client C' à indice 2, 'Client D' à indice 3, 'Client E' à indice 0 (circulaire)

print(f"File pleine ? {ma_file_bornee.est_pleine()}") # True

# Test d'ajout sur file pleine
try:
    ma_file_bornee.ajouter("Client F")
except IndexError as e:
    print(f"Erreur attendue : {e}")

print(f"\nRetrait : {ma_file_bornee.retirer()}") # Attendu: Client B
print(f"Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 3, Premier: 2, Tableau: [None, None, 'Client C', 'Client D']

print(f"Retrait : {ma_file_bornee.retirer()}") # Attendu: Client C
print(f"Retrait : {ma_file_bornee.retirer()}") # Attendu: Client D
print(f"Retrait : {ma_file_bornee.retirer()}") # Attendu: Client E (le dernier via l'enroulement)

print(f"Nbr éléments: {ma_file_bornee.nb_elements}, Premier indice: {ma_file_bornee.premier_indice}, Tableau: {ma_file_bornee.tableau}")
# Attendu: Nbr: 0, Premier: 1 (revient à 1 après avoir retiré E), Tableau: [None, None, None, None]
print(f"File vide ? {ma_file_bornee.est_vide()}") # True

# Test de retrait sur file vide
try:
    ma_file_bornee.retirer()
except IndexError as e:
    print(f"Erreur attendue : {e}")
print("-" * 20)

import random

# Réutilisation d'une classe File simple (listes Python pour faciliter l'exercice)
# Pour une vraie simulation à grande échelle, la FileBornee serait mieux.
class FileSimple:
    def __init__(self):
        self.elements = []
    def est_vide(self):
        return len(self.elements) == 0
    def ajouter(self, e):
        self.elements.append(e)
    def retirer(self):
        if self.est_vide():
            raise IndexError("retirer d'une file vide")
        return self.elements.pop(0) # pop(0) est O(N) mais suffisant pour la démo
    def taille(self):
        return len(self.elements)

# --- Paramètres de la simulation ---
N_GUICHETS = 5
DUREE_SIMULATION = 100000 # Tours d'horloge

# --- Simulation 1 : Une seule file d'attente pour tous les guichets ---
def simuler_unique_file():
    print("\n--- Simulation : Une seule file d'attente pour tous les guichets ---")
    
    file_unique = FileSimple()
    disponibilite_guichets = [0] * N_GUICHETS # Temps avant que le guichet soit libre
    
    total_attente = 0
    clients_servis = 0
    
    for horloge_globale in range(DUREE_SIMULATION):
        # 1. Apparition d'un nouveau client (son heure d'arrivée est l'horloge actuelle)
        file_unique.ajouter(horloge_globale) # Le client arrive à l'heure 'horloge_globale'

        # 2. Pour chaque guichet
        for i in range(N_GUICHETS):
            if disponibilite_guichets[i] == 0: # Guichet i est libre
                if not file_unique.est_vide(): # Y a-t-il un client à servir ?
                    heure_arrivee_client = file_unique.retirer()
                    attente_client = horloge_globale - heure_arrivee_client
                    
                    total_attente += attente_client
                    clients_servis += 1
                    
                    # Le guichet devient occupé pour un temps aléatoire (entre 0 et N_GUICHETS)
                    disponibilite_guichets[i] = random.randint(0, N_GUICHETS)
            else:
                # Guichet occupé, décrémente son temps d'occupation
                disponibilite_guichets[i] -= 1
    
    print(f"Clients servis : {clients_servis}")
    print(f"Temps d'attente cumulé : {total_attente}")
    if clients_servis > 0:
        temps_attente_moyen = total_attente / clients_servis
        print(f"Temps d'attente moyen : {temps_attente_moyen:.2f}")
    else:
        print("Aucun client servi.")

# --- Simulation 2 : Une file d'attente par guichet (choix aléatoire) ---
def simuler_multi_files_aleatoire():
    print("\n--- Simulation : Une file d'attente par guichet (choix aléatoire) ---")
    
    files_guichets = [FileSimple() for _ in range(N_GUICHETS)] # Une liste de files
    disponibilite_guichets = [0] * N_GUICHETS
    
    total_attente = 0
    clients_servis = 0
    
    for horloge_globale in range(DUREE_SIMULATION):
        # 1. Apparition d'un nouveau client
        # Le client choisit un guichet au hasard pour sa file
        guichet_choisi = random.randint(0, N_GUICHETS - 1)
        files_guichets[guichet_choisi].ajouter(horloge_globale)

        # 2. Pour chaque guichet
        for i in range(N_GUICHETS):
            if disponibilite_guichets[i] == 0: # Guichet i est libre
                if not files_guichets[i].est_vide(): # Y a-t-il un client dans SA file ?
                    heure_arrivee_client = files_guichets[i].retirer()
                    attente_client = horloge_globale - heure_arrivee_client
                    
                    total_attente += attente_client
                    clients_servis += 1
                    
                    disponibilite_guichets[i] = random.randint(0, N_GUICHETS)
            else:
                disponibilite_guichets[i] -= 1
    
    print(f"Clients servis : {clients_servis}")
    print(f"Temps d'attente cumulé : {total_attente}")
    if clients_servis > 0:
        temps_attente_moyen = total_attente / clients_servis
        print(f"Temps d'attente moyen : {temps_attente_moyen:.2f}")
    else:
        print("Aucun client servi.")

# --- Simulation 3 : Une file d'attente par guichet (choix de la file la plus courte) ---
def simuler_multi_files_plus_courte():
    print("\n--- Simulation : Une file d'attente par guichet (choix de la file la plus courte) ---")
    
    files_guichets = [FileSimple() for _ in range(N_GUICHETS)]
    disponibilite_guichets = [0] * N_GUICHETS
    
    total_attente = 0
    clients_servis = 0
    
    for horloge_globale in range(DUREE_SIMULATION):
        # 1. Apparition d'un nouveau client
        # Le client choisit la file la plus courte
        min_taille = float('inf') # Infini pour trouver le minimum
        indice_file_plus_courte = 0
        for i in range(N_GUICHETS):
            if files_guichets[i].taille() < min_taille:
                min_taille = files_guichets[i].taille()
                indice_file_plus_courte = i
        
        files_guichets[indice_file_plus_courte].ajouter(horloge_globale)

        # 2. Pour chaque guichet
        for i in range(N_GUICHETS):
            if disponibilite_guichets[i] == 0: # Guichet i est libre
                if not files_guichets[i].est_vide(): # Y a-t-il un client dans SA file ?
                    heure_arrivee_client = files_guichets[i].retirer()
                    attente_client = horloge_globale - heure_arrivee_client
                    
                    total_attente += attente_client
                    clients_servis += 1
                    
                    disponibilite_guichets[i] = random.randint(0, N_GUICHETS)
            else:
                disponibilite_guichets[i] -= 1
    
    print(f"Clients servis : {clients_servis}")
    print(f"Temps d'attente cumulé : {total_attente}")
    if clients_servis > 0:
        temps_attente_moyen = total_attente / clients_servis
        print(f"Temps d'attente moyen : {temps_attente_moyen:.2f}")
    else:
        print("Aucun client servi.")

# --- Exécution des simulations ---
print("Exercice 22 : Simulation d'Attente aux Guichets")
simuler_unique_file()
simuler_multi_files_aleatoire()
simuler_multi_files_plus_courte()
print("-" * 20)