Parenthésage correct

Exercice conseillé en version À compléter
  • Les exercices conseillés en version "Vide" sont conçus pour ressembler à un "exercice 1" des épreuves pratiques au baccalauréat de Terminale NSI.
  • Les exercices conseillés en version "À compléter" sont conçus pour ressembler à un "exercice 2" des épreuves pratiques au baccalauréat de Terminale NSI.

La difficulté de l'exercice a été choisie en partant du principe qu'il est fait dans la version indiquée.

Dans cet exercice, on étend le problème de parenthésage à l'ensemble des délimiteurs, à savoir parenthèses, crochets et accolades.

On dispose de chaînes de caractères contenant uniquement :

  • des parenthèses ouvrantes '(' et fermantes ')',

  • des crochets ouvrants '[' et fermants ']',

  • des accolades ouvrantes '{' et fermantes '}'.

Un parenthésage est correct si :

  • pour chaque délimiteur, le nombre de fermants coïncide avec le nombre d'ouvrants,
  • en parcourant la chaîne de gauche à droite, pour chaque délimiteur, le nombre d'ouvrants est à tout moment supérieur ou égal au nombre de fermants,
  • les différents délimiteurs ne s'entre-croisent pas, par exemple '[(])' est incorrect.

Bien parenthésées

  • (2 + 4)*7
  • tableau[f(i) - g(i)]
  • #include <stdio.h> int main(){int liste[2] = {4, 2}; return (10*liste[0] + liste[1]);}

Mauvais parenthésage

  • (une parenthèse laissée ouverte ; pas de fermante associée à (.
  • {<(}>) ; mauvaise imbrication.
  • c'est trop tard ;-) ; pas d'ouvrante associée à ).

On souhaite programmer une fonction est_bien_delimitee qui prend en paramètre une chaîne de délimiteurs expression et renvoie True ou False selon qu'elle est correctement délimitée ou non.

On utilise un dictionnaire pour associer facilement délimiteurs fermants et ouvrants.

Exemples 
>>> est_bien_delimitee('([()[]]{()})')
True
>>> est_bien_delimitee('{}[(])')
False
>>> est_bien_delimitee('[][')
False
>>> est_bien_delimitee('[]]')
False

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013beqn,49vi[3mo5_tx;Ph}klpw!f(: cg.a=ry0FS6]u/72){s18d050!0c0q0I0j0x0X0E0F0x0I0X0X0J010q0j0y010406050X0R0m0m0I0K0L040O0n0x0R0^0n0e050S0 1113150}0y04051l1e1o0S1l0}0!0j0i0-0/0;0?0u0j0G0u0x1C0u0q0{050(0b0x0c1x0:0=011B1D1F1D0q1L1N1J0q0K1m0q0u0-180X0y0I0e0?0U011P1z010B0*0c0e0I0m0c1J1,1.1?1R1_1N1|1~0{0a0E0t0K0n0y0n0X0j1b0e0E0$1*0K0K0c0F2j1e210e1m0S1(2w1#1%1$1K0!230?1F0e1{2g1J1u1w0.1Q2G0j2I0e0n2M1J0y2p1m2u2w2!0~1-2k2O1@2T0K120x0{0E0Y2t2(0|2%222*1R2,2.2:0U2?1.2^2u2F012}0I2/040E0l312v0}342{0?37390E0g3d332(353j2:0o3n3f3p3h360n2-382:0P3u2_2)1y2|3z2~3a0T3E3g3H3i3J3B3a0Z3N3w3P3y3A3k0h3V2`3X3r040Y0M3$3G2P3Y3K0Y2=1f2@3v3%3/3)0Y303@323_3.2+3R390Y3c3 3e3F3q440{0Y3m482w2X0c2w2M2z0!1%2E3x0F2U1 1m4l1n2Y3F2#2@054r0$2Z3W3/0w0{0$0B3n4a3x0z2:4L3O3{0B0{0c0X0q0p0b0j1{0p0$1F0m2i0c0c4Q4F1@0`040C4-3`2+4U0r4i0;0j1c4?421R4:0V0D3u0E560E4M3(0{0n0R0i0K1.0q0X3n584R1@0n0{0J5j593/4:0W4 350X1;04020d0R0n0q0s0V5A5C5E5v3x4:544g5k4.1R5x0{5H5D0s0C5U5J4g5r4/0{0f5q5l5R5y5Y0s0Q5-5K3X5M5)5Q0?5S5z5B5V0k5:5!5*0?4:5(5O5#5+5T5|5E0v5 2$61015?656e5`5-0W6c4A6e4:0v3u06575P4@2|0{0y1`5@6v0?5n045p6h5^360{0t6z606H4:0C0V5557660?4H040B3z6A503i4I0c4(4*0R0K6Z350n4O042R6,3x0e4_4{2h4~6M6B6f0{5N2!6s6t6S6e6V0j4K6G6}6@044%0j4)0q0c6*6=3X6.0{6;796!016j695W0k6l7s5;5s6 6R73736T6I046y1N7x5m0{0H7I6w040c0m7G4,6|7p6O7M6#7c6%7e6)6+7T35527A7C754U0+7S6d6N7z4g727B6t7D76782!6u7p7b7R7W016D7L7%6?4U4W0p0i0j0$826O537*7^7+6H6V2p0q6*1d7o350w0F0{0N380X7/3^8i7_7,7O1F7|2@7~3q6x6L7:6}84827b0$81865=0{6P7j3/6D0A6F7}7D7b5c5e5g5i8S7y040k8O6$6(7g7i8,5$040Q708z8A7B7`0{8m8o8W1@8s8u8w8y407@8H3x8l0%938q877F8K6n6H8N8^7N4V4X8b8d9o628U6Q7?1e4C4j1p4x0S4v2x4n1e2A9I0I1M9B9E1v2^9E0%0)0+04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013beqn,49vi[3mo5_tx;Ph}klpw!f(: cg.a=ry0FS6]u/72){s18d050!0c0q0I0j0x0X0E0F0x0I0X0X0J010q0j0y010406050X0R0m0m0I0K0L040O0n0x0R0^0n0e050S0 1113150}0y04051l1e1o0S1l0}0!0j0i0-0/0;0?0u0j0G0u0x1C0u0q0{050(0b0x0c1x0:0=011B1D1F1D0q1L1N1J0q0K1m0q0u0-180X0y0I0e0?0U011P1z010B0*0c0e0I0m0c1J1,1.1?1R1_1N1|1~0{0a0E0t0K0n0y0n0X0j1b0e0E0$1*0K0K0c0F2j1e210e1m0S1(2w1#1%1$1K0!230?1F0e1{2g1J1u1w0.1Q2G0j2I0e0n2M1J0y2p1m2u2w2!0~1-2k2O1@2T0K120x0{0E0Y2t2(0|2%222*1R2,2.2:0U2?1.2^2u2F012}0I2/040E0l312v0}342{0?37390E0g3d332(353j2:0o3n3f3p3h360n2-382:0P3u2_2)1y2|3z2~3a0T3E3g3H3i3J3B3a0Z3N3w3P3y3A3k0h3V2`3X3r040Y0M3$3G2P3Y3K0Y2=1f2@3v3%3/3)0Y303@323_3.2+3R390Y3c3 3e3F3q440{0Y3m482w2X0c2w2M2z0!1%2E3x0F2U1 1m4l1n2Y3F2#2@054r0$2Z3W3/0w0{0$0B3n4a3x0z2:4L3O3{0B0{0c0X0q0p0b0j1{0p0$1F0m2i0c0c4Q4F1@0`040C4-3`2+4U0r4i0;0j1c4?421R4:0V0D3u0E560E4M3(0{0n0R0i0K1.0q0X3n584R1@0n0{0J5j593/4:0W4 350X1;04020d0R0n0q0s0V5A5C5E5v3x4:544g5k4.1R5x0{5H5D0s0C5U5J4g5r4/0{0f5q5l5R5y5Y0s0Q5-5K3X5M5)5Q0?5S5z5B5V0k5:5!5*0?4:5(5O5#5+5T5|5E0v5 2$61015?656e5`5-0W6c4A6e4:0v3u06575P4@2|0{0y1`5@6v0?5n045p6h5^360{0t6z606H4:0C0V5557660?4H040B3z6A503i4I0c4(4*0R0K6Z350n4O042R6,3x0e4_4{2h4~6M6B6f0{5N2!6s6t6S6e6V0j4K6G6}6@044%0j4)0q0c6*6=3X6.0{6;796!016j695W0k6l7s5;5s6 6R73736T6I046y1N7x5m0{0H7I6w040c0m7G4,6|7p6O7M6#7c6%7e6)6+7T35527A7C754U0+7S6d6N7z4g727B6t7D76782!6u7p7b7R7W016D7L7%6?4U4W0p0i0j0$826O537*7^7+6H6V2p0q6*1d7o350w0F0{0N380X7/3^8i7_7,7O1F7|2@7~3q6x6L7:6}84827b0$81865=0{6P7j3/6D0A6F7}7D7b5c5e5g5i8S7y040k8O6$6(7g7i8,5$040Q708z8A7B7`0{8m8o8W1@8s8u8w8y407@8H3x8l0%938q877F8K6n6H8N8^7N4V4X8b8d9o628U6Q7?1e4C4j1p4x0S4v2x4n1e2A9I0I1M9B9E1v2^9E0%0)0+04.
Indice 1

On utilisera une pile qui empile les ouvrants, dépile un ouvrant dès qu'un fermant est rencontré en vérifiant la correspondance, et qui ignore les autres caractères.

La classe Pile est fournie ci-dessous. Elle est déjà "chargée" en mémoire et donc utilisable sans import dans la zone de saisie.

La classe Pile 
class Pile:
    def __init__(self):
        """Initialise une pile vide"""
        self.valeurs = []

    def est_vide(self):
        """Renvoie un booléen : la pile est-elle vide ?"""
        return len(self.valeurs) == 0

    def empile(self, element):
        """Empile un élément au sommet de la pile"""
        self.valeurs.append(element)

    def depile(self):
        """
        Dépile un élément au sommet et le renvoie.
        Provoque une erreur si la pile est vide.
        """
        if self.est_vide():
            raise ValueError("Erreur, pile vide")
        else:
            return self.valeurs.pop()

    def __repr__(self):
        """Affiche la pile, en indiquant le sommet"""
        return f"| {' | '.join([str(x) for x in self.valeurs])} | <- sommet"
Indice 2

On adopte la démarche suivante utilisant une Pile :

  • on parcourt les caractères de la chaîne,
  • si le caractère lu est un délimiteur ouvrant on l'empile,
  • si c'est un délimiteur fermant :
    • si la pile est vide, on renvoie False,
    • sinon, si le caractère dépilé n'est pas le délimiteur ouvrant du caractère lu, on renvoie False,
  • à la fin du parcours, si la pile est vide on renvoie True, sinon False.