Parenthésage correct

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

.128013nb1lu=h. P4580S7p9_(6[!ex]yvfm{k)cFirwd/3:}gats2,o050N0y0U0T0K0e0V0j0I0e0T0V0V0g010U0K0r010406050V0f0E0E0T0L0B040p0Y0e0f0?0Y0b050O0}0 11130{0r041c1j051m0O1m1o1j0{0N0K0C0+0-0/0;0h0K0S0h0e1C0h0U0_050$0c0e0y1x0.0:011B1D1F1D0U1L1N1J0U0c0Y0N131K0L1k0U0h0+160V0r0T0b0;0W011P1z010D0(0y0b0T0E0y1J1;1?1{1R1~1N21230_0a0j0k0L0Y0r0Y0V0K190b0j0!1/0L0L0y0I2o1c260b1k0O1-2B0U1+1*1,0N280;1F0b202l1J1u1w0,1Q2L0K2N0b1%1v1J0r2u1k2z2B2)0|1=2p2T1|2Y0L100e0_0j0d2y2-0`2,272/1R2;2?2^0W2{1?2}2z2K01320T2@040j0P362A0{39300;3c3e0j0l3i382-3a3o2^0m3s3k3u3m3b0Y2=3d2^0v3z2~2.1y313E333f0q3J3l3M3n3O3G3f0n3S3B3U3D3F3p0s3!2 3$3w040d0o3+3L2U3%3P0d2`1d2|3A3,3@3.0d353|373~3?2:3W3e0d3h443j3K3v490_0d3r4d2B2$0y2B2R2E0N2I3a0I1%241k4q1n2%3K2*2|054v0!2(3#3@0G0_0!0D3s4f3C0M2^4P3T400D0_0y0V0U0t0c0K200t0!1F0E2n0y0y4U4J1|0^040u4;3 2:4Y0z4n0/0K1a4`471R4@0H0Q3z0j5a0j4Q3-0_0Y0f0C0L1?0U0V3s5c4V1|0Y0_0g5n5d3@4@0F533a0V1_04010H015z3C4@584l5o4=1R5B0_010u5G4l5v4?0_0X5u5p5O5C010A5T2+5!0;5J5Z5N0;5P5D0w5)4E5+014@5Y5L5V5#5Q0R5@375~5,0_5K2)5M4{5 5D0F622A645`0_0R3z065b69543n0_0r1 5.6a0;5r045t5}5_0b0_0k6s5U5_4@0u0H595b6g4L040D3E6t6o3b4M0y4,4.0f0L6R3a0Y4S042W6!3C6B040y4~2u50526F5/6h04673}6m6m6M0_0K4O6z6@6,4+0K4-0U0y6Y6*3$6$6 1b726u015;5R0w6d5H3$5-4l6l6|7s6g6,6r1N7n3@6w0i7y4|6-0E7w4:6?7h6H7C316U6W787a7I6S566K7t5_6N6V0V7H5*6@7p2)7r7s6}7W6 71687u6q6E7#7h7A7L6p6-4!0t0C0K0!7_6^6I6`457*866n3a6N2u0U6Y7f7/7W0I0_0J3d7Z7U876~6-1F7.2|886+7;7x7R6#0_7B8x8u040!7G816H6J7g6S6w0x6y8f735f5h5j0b5l8G0_0w81746V766X6Z8B7o0_0A843j877*8o8b8d7b4K8h048j0)7!3}7)8t3$8a0#8=8J3v8v8|635_7^8(404Y7|7~809b5W4^8I7(1c4G4o1l4B0O4z2C4s1c2F2E1$1(2E0T1M9o9r1v2}9r0#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

.128013nb1lu=h. P4580S7p9_(6[!ex]yvfm{k)cFirwd/3:}gats2,o050N0y0U0T0K0e0V0j0I0e0T0V0V0g010U0K0r010406050V0f0E0E0T0L0B040p0Y0e0f0?0Y0b050O0}0 11130{0r041c1j051m0O1m1o1j0{0N0K0C0+0-0/0;0h0K0S0h0e1C0h0U0_050$0c0e0y1x0.0:011B1D1F1D0U1L1N1J0U0c0Y0N131K0L1k0U0h0+160V0r0T0b0;0W011P1z010D0(0y0b0T0E0y1J1;1?1{1R1~1N21230_0a0j0k0L0Y0r0Y0V0K190b0j0!1/0L0L0y0I2o1c260b1k0O1-2B0U1+1*1,0N280;1F0b202l1J1u1w0,1Q2L0K2N0b1%1v1J0r2u1k2z2B2)0|1=2p2T1|2Y0L100e0_0j0d2y2-0`2,272/1R2;2?2^0W2{1?2}2z2K01320T2@040j0P362A0{39300;3c3e0j0l3i382-3a3o2^0m3s3k3u3m3b0Y2=3d2^0v3z2~2.1y313E333f0q3J3l3M3n3O3G3f0n3S3B3U3D3F3p0s3!2 3$3w040d0o3+3L2U3%3P0d2`1d2|3A3,3@3.0d353|373~3?2:3W3e0d3h443j3K3v490_0d3r4d2B2$0y2B2R2E0N2I3a0I1%241k4q1n2%3K2*2|054v0!2(3#3@0G0_0!0D3s4f3C0M2^4P3T400D0_0y0V0U0t0c0K200t0!1F0E2n0y0y4U4J1|0^040u4;3 2:4Y0z4n0/0K1a4`471R4@0H0Q3z0j5a0j4Q3-0_0Y0f0C0L1?0U0V3s5c4V1|0Y0_0g5n5d3@4@0F533a0V1_04010H015z3C4@584l5o4=1R5B0_010u5G4l5v4?0_0X5u5p5O5C010A5T2+5!0;5J5Z5N0;5P5D0w5)4E5+014@5Y5L5V5#5Q0R5@375~5,0_5K2)5M4{5 5D0F622A645`0_0R3z065b69543n0_0r1 5.6a0;5r045t5}5_0b0_0k6s5U5_4@0u0H595b6g4L040D3E6t6o3b4M0y4,4.0f0L6R3a0Y4S042W6!3C6B040y4~2u50526F5/6h04673}6m6m6M0_0K4O6z6@6,4+0K4-0U0y6Y6*3$6$6 1b726u015;5R0w6d5H3$5-4l6l6|7s6g6,6r1N7n3@6w0i7y4|6-0E7w4:6?7h6H7C316U6W787a7I6S566K7t5_6N6V0V7H5*6@7p2)7r7s6}7W6 71687u6q6E7#7h7A7L6p6-4!0t0C0K0!7_6^6I6`457*866n3a6N2u0U6Y7f7/7W0I0_0J3d7Z7U876~6-1F7.2|886+7;7x7R6#0_7B8x8u040!7G816H6J7g6S6w0x6y8f735f5h5j0b5l8G0_0w81746V766X6Z8B7o0_0A843j877*8o8b8d7b4K8h048j0)7!3}7)8t3$8a0#8=8J3v8v8|635_7^8(404Y7|7~809b5W4^8I7(1c4G4o1l4B0O4z2C4s1c2F2E1$1(2E0T1M9o9r1v2}9r0#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.