Aller au contenu

Vérification syntaxique de parenthèses ou de balises

D'après 2022, Métropole, J1, Ex. 1

Partie A : Expression correctement parenthésée⚓︎

On veut déterminer si une expression arithmétique est correctement parenthésée. À chaque parenthèse fermante ")" correspond une parenthèse précédemment ouverte "(".

Exemples

  • L'expression arithmétique "(2 + 3) × (18/(4 + 2))" est correctement parenthésée.
  • L'expression arithmétique "(2 + 3) × (18/(4 + 2" est non correctement parenthésée.

Pour simplifier les expressions arithmétiques, on enregistre, dans une structure de données, uniquement les parenthèses dans leur ordre d'apparition. On appelle expression simplifiée cette structure.

Expression arithmétique Structure de données
"(2 + 3) × (18/(4 + 2))" ()(())

1. Indiquer si la phrase « les éléments sont maintenant retirés (pour être lus) de cette structure de données dans le même ordre qu'ils y ont été ajoutés lors de l'enregistrement » décrit le comportement d'une file ou d'une pile. Justifier.

Réponse

Le premier à être retiré était le premier à être ajouté, donc cela correspond à une file.

Pour vérifier le parenthésage, on peut utiliser une variable controleur qui :

  • est un nombre entier égal à 0 en début d'analyse de l'expression simplifiée ;
  • augmente de 1 si l'on rencontre une parenthèse ouvrante "(" ;
  • diminue de 1 si l'on rencontre une parenthèse fermante ")".

Exemple

On considère l'expression simplifiée A : "()(())"

Lors de l'analyse de l'expression A, controleur (initialement égal à 0) prend successivement pour valeur 1, 0, 1, 2, 1, 0.

Le parenthésage est correct.

2. Écrire, pour chacune des 2 expressions simplifiées B et C suivantes, les valeurs successives prises par la variable controleur lors de leur analyse.

  • Expression simplifiée B : " ((()()"
  • Expression simplifiée C : "(()))("
Réponse
  • Expression simplifiée B : 1, 2, 3, 2, 3, 2
  • Expression simplifiée C : 1, 2, 1, 0, -1, 0

3. L'expression simplifiée B précédente est mal parenthésée (parenthèses fermantes manquantes) car le controleur est différent de zéro en fin d'analyse.
L'expression simplifiée C précédente est également mal parenthésée (parenthèse fermante sans parenthèse ouvrante) car le controleur prend une valeur négative pendant l'analyse.

Recopier et compléter uniquement les lignes 13 et 16 du code ci-dessous pour que la fonction parenthesage_correct réponde à sa description.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def parenthesage_correct(expression):
    """ fonction renvoyant True si l'expression arithmétique
    simplifiée (str) est correctement parenthésée, False sinon.
    Condition: expression ne contient que
      des parenthèses ouvrantes et fermantes
    """
    controleur = 0
    for parenthese in expression:  # pour chaque parenthèse
        if parenthese == '(':
            controleur = controleur + 1
        else:  # parenthese == ')'
            controleur = controleur - 1
            if controleur ... :  # test 1 (à recopier et compléter)
                # parenthèse fermante sans parenthèse ouvrante
                return False
    return controleur ...  # test 2 (à recopier et compléter)
    # test 2 est un booléen renvoyé
    #   True : le parenthésage est correct
    #   False : parenthèse(s) fermante(s) manquante(s)
Réponse
  • ligne 13: (controleur < 0)
  • ligne 16: (controleur == 0)

Les parenthèses sont inutiles.

Partie B : Texte correctement balisé⚓︎

On peut faire l'analogie entre le texte simplifié des fichiers HTML (uniquement constitué de balises ouvrantes <nom> et fermantes </nom>) et les expressions parenthésées : par exemple, l'expression HTML simplifiée : "<p><strong><em></em></strong></p>" est correctement balisée.

On ne tiendra pas compte dans cette partie des balises ne comportant pas de fermeture comme <br> ou <img ...>.

Afin de vérifier qu'une expression HTML simplifiée est correctement balisée, on peut utiliser 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).

Exemple

État de la pile lors du déroulement de cet algorithme pour l'expression simplifiée "<p><em></p></em>" qui n'est pas correctement balisée.

État de la pile lors du déroulement de l'algorithme

Parcours de l'expression
"<p><em></p></em>"
↑
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&nbsp;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></p></em>"
  ↑                  Balise <p>  ouvrante, on empile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&lt;p&gt;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></p></em>"
     ↑               Balise <em> ouvrante, on empile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&lt;em&gt;<br>&lt;p&gt;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></p></em>"
          ↑          Balise </p> fermante, on dépile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&lt;p&gt;<br>=====<br>Pile"]

<em> et </p> ne correspondent pas !

Le balisage est incorrect.

4. Cette question traite de l'état de la pile lors du déroulement de l'algorithme.

4.a. Représenter la pile à chaque étape du déroulement de cet algorithme pour l'expression "<p><em></em></p>" (balisage correct).

Réponse
Parcours de l'expression
"<p><em></em></p>"
↑
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&nbsp;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></em></p>"
  ↑                  Balise  <p>  ouvrante, on empile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&lt;p&gt;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></em></p>"
      ↑              Balise  <em> ouvrante, on empile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&lt;em&gt;<br>&lt;p&gt;<br>=====<br>Pile"]
Parcours de l'expression
"<p><em></em></p>"
          ↑          Balise </em> fermante, on dépile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&lt;p&gt;<br>=====<br>Pile"]

<em> et </em> se correspondent.

Parcours de l'expression
"<p><em></em></p>"
               ↑     Balise </p>  fermante, on dépile
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&nbsp;<br>=====<br>Pile"]

<p> et </p> se correspondent.

Parcours de l'expression
"<p><em></em></p>"
                 ↑
flowchart TD
    A["&nbsp;<br>&nbsp;<br>&nbsp;<br>&nbsp;<br>=====<br>Pile"]

La pile est vide. Le balisage est correct.

4.b. Indiquer quelle condition simple (sur le contenu de la pile) permet alors de dire que le balisage est correct lorsque toute l'expression HTML simplifiée a été entièrement parcourue, sans que l'analyse ne s'arrête.

Réponse

Il suffirait de vérifier que la pile est vide.

5. Une expression HTML correctement balisée contient 12 balises.

Indiquer le nombre d'éléments que pourrait contenir au maximum la pile lors de son analyse.

Réponse

6 éléments au maximum seront empilés, dans le cas où 12 balises HTML sont imbriquées. 6 ouvrantes qui seront empilées, puis les 6 fermantes.