NSI - Terminale - les piles et les files

Travail demandé

Partie 1: les Piles

Dans cette partie vous allez concevoir (en partie) un analyseur syntaxique de balises HTML. On peut utiliser une pile pour vérifier la cohérence d'une expression HTML, c'est ce que vous allez développer ici.

L'expression "bonjour tout le monde " est correcte, toutes les balises sont bien orthographiées et les balises en paire refermées dans le bon ordre.
L'expression " bonjour" n'est pas correcte, la balise </p est mal orthographiée
L'expression " bonjour " n'est pas correcte, la balise  referme le paragraphe alors que la balise  texte en gras n'est pas refermée

Question 1:

Avant de pouvoir analyser une expression html, il faut d'abord analyser chaque balise pour définir si elle est ouvrante ou fermante et extraire son nom. On vous donne, ci-dessous, le code de la fonction extraire_balises(expression) qui prend en argument une chaine de caractères constituées de balises comme par exemple "bonjour tout le monde "
La fonction renvoie une liste de tuples avec dans chaque tuple, la nature de la balise (ouvrante ou fermante) et son nom (b, p, h1, etc...).

def extraire_balises(expression):
"""
Analyse la chaîne caractère par caractère pour extraire les balises HTML.
Retourne une liste de tuples (type_balise, nom_balise).
Si une balise est mal formée → retourne [].
"""

balises = []
i = 0
n = len(expression)

while i < n:
    if expression[i] == "<":
        j = i + 1

        # Cherche la fin de la balise
        while j < n and expression[j] != ">":
            j += 1

        # Pas de '>' → balise incomplète
        if j == n:
            print("Erreur : balise incomplète (pas de '>').")
            return []

        # Contenu entre < et >
        contenu = expression[i+1 : j].strip()

        # Si le contenu contient un '<', c'est une balise mal formée
        if "<" in contenu:
            print(f"Erreur : expression mal formée : <{contenu}>")
            return []

        # Détection du type
        if contenu.startswith("/"):
            type_balise = "/"
            contenu = contenu[1:].strip()
        else:
            type_balise = ""

        # Extraction du nom de la balise
        nom = ""
        for c in contenu:
            if c.isalnum():
                nom += c
            else:
                break

        if nom == "":
            print(f"Erreur : balise sans nom valide : <{contenu}>")
            return []

        balises.append((type_balise, nom))

        i = j + 1
    else:
        i += 1

return balises

Tester le code de la fonction pour l'expression " bonjour "
Préciser comment est représenté une balise ouvrante dans le tuple renvoyé et comment est représenté une balise fermante.
Tester le code de la fonction pour l'expression "bonjour tout le monde ", le résultat est-il conforme à votre réponse précédente.

Question 2:

On désire tester la correction du code de la fonction précédente avec des assertions.
Précision: correction du code veut dire que le code donne le bon résultat

Compléter le code de la fonction test_extraire_balises() ci-dessous pour vérifier que toutes les parties du code sont fonctionnelles et tester votre code.

def test_extraire_balises():
    assert extraire_balises("<p> bonjour </p>") ==  [('', 'p'), ('/', 'p')]
    # ajouter au moins deux assertions
    # qui vérifient les différents return possibles
    ...............................
    ...............................
    print("assertions OK")


test_extraire_balises()

Question 3:

Afin de vérifier qu’une expression HTML est correctement balisée, on utilise une pile (initialement vide) selon l’algorithme suivant :

On parcourt successivement chaque balise de l’expression :

lorsque l’on rencontre une balise ouvrante, on l’empile ;
lorsque l’on rencontre une balise fermante:
si la pile est vide, alors l’analyse s’arrête : le balisage est incorrect,
sinon, on dépile et on vérifie que les deux balises (la balise fermante rencontrée et la balise ouvrante dépilée) correspondent (c’est-à-dire ont le même nom) si ce n’est pas le cas, l’analyse s’arrête (balisage incorrect).

Il faut donc créer une pile. On décide d'utiliser le modèle objet.
La classe Pile définit un attribut appelé elements qui lors de la construction de l'objet Pile est associé à un objet liste qui sera le conteneur de la pile.

On vous donne ci-dessous un code compléter de la classe Pile:

class Pile:
    def __init__(self):
        # attribut elements associé à liste vide
        self.elements = []

    def est_vide(self):
        # renvoie True si pile vide sinon renvoie False
        return len(self.elements) == 0

    def empiler(self, balise):
        # à compléter: ajoute balise dans le conteneur
        ............

    def depiler(self):
        # à compléter: si pile vide renvoie None 
        if ...............:
            return None
        # à compléter: dépiler l'élément au sommet de la pile 
        return .........................

    ''' __repr__ est une méthode spéciale de Python.
    Elle définit comment l’objet Pile doit être affiché 
    lorsqu’on le représente sous forme de texte.'''

    def __repr__(self):
        return f"{self.elements}"

Compléter le code de la méthode empiler et celui de la méthode dépiler.
Créer un objet Pile appelé pile ( pour être rigoureux créer une instance de la classe Pile et l'assigner à la variable pile)
Empiler la chaine 'b' dans la pile
Empiler la chaine 'br' dans la pile
Afficher votre pile avec le code print(pile)
dépiler l'élément au sommet de la pile
Afficher votre pile avec le code print(pile)

Question 4:

On vous donne ci-dessous le code à compléter de la fonction analyser_html(balises), cette fonction prend en argument une liste de tuples (type_balise, nom_balise) issue de l'analyse d'une expression html par la fonction de la question 1, la fonction analyser_html(balises) utilise une pile et applique l'algorithme décrit au début de la question 3.

    def analyser_html(balises):
    """
    Analyse un balisage HTML simple basé sur une pile.
    Retourne True si le balisage est correct, False sinon.
    """
    # si la liste de tuples n'est pas vide
    if len(balises) > 0:
        '''A compléter: création d'une instance 
        de la classe Pile associée à la variable pile'''
        ............................
        # pour chaque élement du tuple de la liste balises 
        for type_balise, nom_balise in balises:

            # Cas des balises orphelines : <br/> <img/> etc.
            if nom_balise in BALISES_ORPHELINES:
                # On ne les empile pas, elles sont auto-fermantes
                continue

            # A compléter : si Balise ouvrante : <p> <em> <div> on l'empile
            if type_balise == ....:
                pile.empiler(nom_balise)

            # sinon balise fermante : </p> </b> ...
            else:
                # à completer: si la pile est vide, on renvoit False
                if .......................:
                    print(f"Erreur : balise fermante </{nom_balise}> 
                    alors que la pile est vide.")
                    return ..........

                # si la pile n'est pas vide on continue
                # on dépile la balise au sommet de la pile
                balise_ouverte = pile.depiler()
                '''on compare le nom de la balise fermante 
                avec celle le nom de la balise que l'on vient 
                de dépiler, si différent on renvoie False''' 
                if balise_ouverte != nom_balise:
                    print(f"Erreur: 
                    balise ouvrante <{balise_ouverte}> ne correspond 
                    pas à </{nom_balise}>.")
                    return False

        # Si la pile n'est pas vide à la fin → balises non fermées
        if not pile.est_vide():
            print(f"Erreur : balises non fermées : {pile.elements}")
            return False

    return True
else:
    return False

Compléter le code des parties en pointillées dans la fonction (utiliser les commentaires pour savoir quoi coder).

Partie 2: les Files

On cherche à créer une application de type liste de tâches à faire pour aider Alice à planifier sa journée. Pour ça Alice saisit les informations concernant chacune des tâches qu’elle doit effectuer : elle indique un nom pour la tâche et la durée qu’elle estime nécessaire pour la réaliser.

On représentera une tâche saisie par Alice à l’aide d’un objet de type Tache, muni de quatre attributs:
• le numero de la tâche, saisi par Alice;
• le nom de la tâche, saisi par Alice;

• la duree_initiale (un entier exprimé en minute) nécessaire à la réalisation de la tâche saisie par Alice;
• la duree_restante (un entier exprimé en minute) avant la fin de la tâche. Cet attribut sera initialisé avec la durée totale nécessaire à la réalisation de la tâche.

Avancer de n minutes (n entier positif) dans une tâche consiste à diminuer de n la durée restante de cette tâche. Une tâche est terminée si la durée restante est négative ou nulle

Au départ la durée restante est égale à la durée initiale de la tache, par exemple:

On vous donne ci-dessous le code incomplet de la classe Tache:

class Tache: 
    def __init__(self, numero, nom, duree): 
        self.numero = numero 
        self.nom = nom 
        self.duree_initiale = duree 
        self.duree_restante = duree
    def __repr__(self):
        ''' pour la tache numéro = 3 renverra <t3>'''
        return '<t'+str(self.numero)+'>'

    def avancer(self, n): 
        ''' à compléter'''
        ..................

    def est_terminee (self): 
        ''' à compléter'''
        ..................

Question 5:

Ecrire le code Python qui permet d’instancier deux variables tache1 et tache2 représentant les tâches 1 et 2 d'Alice.

Question 6:

Compléter le code de la méthode avancer de la classe Tache qui permet d’avancer la tâche self de n minutes.

Question 7:

Compléter le code de la méthode est_terminee de la classe Tache qui renvoie True si la tâche est terminée, ou False sinon.

Question 8:

Afin d’aider Alice à planifier sa journée, on lui propose d’associer à chacune des tâches une priorité. La priorité d’une tâche est représentée par un entier de la manière suivante : 1 est la priorité minimale et, plus le nombre est grand, plus la tâche associée est prioritaire.

Pour stocker toutes les tâches à effectuer, on utilise une file, dans laquelle les éléments sont des tuples (tache, priorite). Les éléments stockés dans la file doivent respecter les deux conditions ci-après.

• Condition 1 : les éléments sont rangés par ordre décroissant de priorité. L’élément de priorité maximale se trouve au début de la file, l’élément le moins prioritaire se trouve à la fin de la file.

• Condition 2 : parmi les éléments de même priorité, les éléments sont rangés dans l’ordre dans lequel ils ont été insérés dans la file.

Exemple de file: [('<t3>', 4),('<t1>', 3),('<t2>', 3),('<t4>', 1),('<t5>', 1)]

On implémente la file avec le modèle objet, voici le code à compléter de la classe File.

class File: 
    def __init__(self):
        ''' l'attribut taches est associé à un objet liste, 
        qui est le conteneur de la file''' 
        self.taches = []

    def est_vide(self):
        ''' renvoie True si la file est vide et False sinon'''
        # à compléter
        .................

    def enfiler(self, e):
        ''' e est un tuple (<numéro tache>, duree), 
        qui est mis en fin de file'''
        # à compléter
        .................


    def defiler(self):
        ''' renvoie l'élément en tête de file s'il existe
        et le supprime de la file'''
        # à compléter
        .................

    def examiner(self):
        ''' renvoie l'élément en tête de file s'il existe
        sans le suppimer'''
        # à compléter
        .................

Compléter le code des parties en pointillées dans la fonction (utiliser les commentaires pour savoir quoi coder).

Question 9:

Ecrire le code qui ajoutera la tâche 1 puis la tâche 2 d'Alice dans la file, chacune de ces tâches à la priorité 3.

Question 10:

On vous propose d'écrire une fonction ajouter_file_prio(file, p, t) qui prend trois paramètres: une file f dont les éléments sont des tuples (tache, priorite) rangés par ordre de priorité, le deuxième argument est la priorité p d'un nouvel objet tache t passée en troisième argument que l'on souhaiterait insérer. La fonction crée le tuple (<numero tache de t>,p) et l'insère au bon emplacement dans f, c'est à dire en respectant l'ordre la priorité et l'ordre d'arrivée en cas de priorité égale.

Le principe du code de la fonction sera le suivant:
La fonction utilise une file auxiliaire f_aux que l’on remplit en défilant les éléments en début de file f tant que la priorité de l'élément de la file est supérieure ou égale à la priorité p; dès que ce n'est plus vrai, on enfile le nouveau tuple (<numero tache t>,p) dans la file auxiliaire. On défile ensuite tous les éléments restants de f dans f_aux. Il suffit ensuite d'enfiler dans f tous les éléments de f_aux pour avoir la file f avec le nouveau tuple inséré au bon endroit.

Compléter de code de la fonction proposée ci-dessous.

def ajouter_file_prio(f, t, p): 
    # objet file auxiliaire   
    f_aux = File()
    # tant que p est inférieur à la priorité de l'élément examiné de f
    while p < f.examiner()[1]:
        # à compléter: enfiler dans pile auxiliaire element défilé de f  
        ..................................
    # enfiler le nouveau tuple dans file auxiliaire
    f_aux.enfiler((str(t),p))
    # tant que la file f n'est pas vide 
    # enfiler les tuples restants dans file auxiliaire        
    while not f.est_vide():
        ..................................
    # tant que la file auxiliaire n'est pas vide
    # enfiler les tuples de la file auxiliaire dans f  
    while not f_aux.est_vide():
        f.enfiler(f_aux.defiler())

Tester votre fonction en complétant le code ci-dessous:

tache_1 = Tache(1, "Répondre aux textos", 45)
tache_2 = Tache(2, "Ranger ma chambre ", 120)
# tache 3 de priorité 6
tache_3 = Tache(3, "Réviser la NSI ", 90)
f = File()
# ajout de tache 1 et 2 dans f
f.enfiler((str(tache_1), 3))
f.enfiler((str(tache_2), 3))
# a compléter:
.............................

Expliquer ce que vaut f.examiner()[1] si f.taches = [('<t1>', 3),(<'t2>', 3)].