Expression bien parenthésée

On considère dans cet exercice un parenthésage avec les couples (), {}, [] et <>. On dira qu'une expression est bien parenthésée si chaque symbole ouvrant correspond à un symbole fermant et si l'expression contenue à l'intérieur est elle-même bien parenthésée.

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

XKCD 859

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

Écrire une fonction est_bien_parenthesee qui détermine si une expression passée en paramètre est bien parenthésée avec les couples (), {}, [] et <>. La fonction renvoie un booléen. L'expression sera une chaine de caractères de longueur au plus 1000.

Exemples 
1
2
3
4
5
6
>>> est_bien_parenthesee("(2 + 4)*7")
True
>>> est_bien_parenthesee("tableau[f(i) - g(i)]")
True
>>> est_bien_parenthesee("int main(){int liste[2] = {4, 2}; return (10*liste[0] + liste[1]);}")
True

1
2
3
4
5
6
>>> est_bien_parenthesee("(une parenthèse laissée ouverte crée une tension intense qui dure toute la journée.")
False
>>> est_bien_parenthesee("{<(}>)")
False
>>> est_bien_parenthesee("c'est trop tard ;-)")
False

On pourra compléter le code donné qui utilise un dictionnaire ouverture qui renvoie l'élément ouvrant associé à la clé fermante.

Python Console Session
1
2
3
4
>>> ouverture['}']
'{'
>>> ouverture['>']
'<'
###(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 : 5/5
.128013oP;f 8lkg5:z,Fbry2a1}hé3tvw!=u6{e[(Sn9]x_s-c)7iqm./4p0d050%0H0z0t0V0h0Q0f0S0h0t0Q0Q0D010z0V0#010406050Q0E0X0X0t0q0r040K0b0h0E0{0b0L050Z12141618100#04051o1h1r0Z1o100%0V0A0:0=0@0_0=0L0j0E0t0j0H0R0#0r0z0w1f0f0w0V0j0w0h1T0w0z0~050+0p0h0H1A0?0^011S1U1W1U0z1$1(1!0z0q1p1O0:1b0Q0#0t0L0_0s011*1C010e0-0H0L0t0X0H1!1 21261,291(2c2e0~0a0f0c0q0b0#0b0Q0V1e0L0f0)1}0q0q0H0S2z1h2h0L1p0Z1O2M1_1{1`1#0%2j1D0V0L2b2w1!1x1z0;1+2W2Y0L0b2$1!0#2F1p2K2M2?11202A2(272,0q150h1!0t1R2F0e0_030P0P0S2-0H1W2+0b0R0y0R0u0~0f0u1h0t2@2`0 2_2i2|1,2~3032340H3601383a3c3e2Z3h0R24040f0s3o3q213s2K2V013x0t311p330w3537393b0)3H2,3J0y3l0y3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0!3l0!3;1i3?3t2{1B3w0b2 3X3z3#3B3%3F3*433,3i0k3l0k492?3@2`3U3{4j3 3E3)3d4p3g3i0F3l0F4v4b3^4e3`4g3y3Z3A3C4D423f3J0U3l0U4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0g3l0g4%2L4)4d2)4,4h3|3~4l404n4F4@0R0M3l0M4|3S4y3_514S3}4U4m4E3+4H3j0$0~0u0$5e4~4z4-535l565n4G3J0u3k045F5v4c5x524B554W4?443j3L0u3O0Z3p3=4(5K5h4A4/4C4=585R0u3.5H3:5W3Q4}5!4+5$5k4:5m4X5+465H485:5Y5=4O505^544;575o5E4s5H4u614a3R1s2;1h2$2P0%1{2U5h4E2#1y1p2:0H2=3r621p4E6x2i0V0%0_392K5E3z6E6G695D3i3k0f2n0H6M5C595G3;642}0~0b0E0A0q210z6z0f5?500b0~0D6,6.270Q3L010J0I0G020h0z0d016z106g2L5K6L016H2`3J3L5k795)6a3i246R2d6T7a6N597e616Z3w0~0e0H4h0L6+763M6@1,6:046=7B6-7t0_6_0~010T0N0v020j71737B752^3T7g0P6I3i5-7f6F7o6V5R3.7l2e6U5|4q3h1!7s5g5@6#6%7x0z0E2F6?7K017F7H2?7J7`500}040G6z7D3`7v8e838b0l82896!040b8m4*500i7v4g8r4 8o8q7B8f018b0n8x4z8h7I8C0b0B0~2X8G5#0p0~0m0|8i8n1,8b0J8V8s8z6%6)7z8!8y8X0~8F8J830L7v7x158)8B8j0~0T0v748*0f7!7$0R5~7)7;5Q7?467/7n7h6O937^3p7X6y7Z7*7b213J6c957+7=5p4s9a965*7?9o7_8#1,0i8;040e2t0X8 5h8M7C8_8W3`9D3b0h1(2H0V1f0Q9I4+9K6-9M9A0_9C8N0X2v0q7A878C9D0)0W0E0H8P4+0S5G030f0#8?0*2B001d0-0V0Q7x2B0H9=1)9=0V909*0h0x2e7z1)0#2a0/a02l0H9W7W8 917c4I6K9k7p5R4J9u9q975p4J2M5X839`0~9|2x2,2A0-0faq0z9}2w2x1%1)0%a20{1Wa60q0f1(0/a$0zaq2r1N1P1gas9#aPay924!4T7!7,7?4!aC9c59a{6Y9N018u040)0e9X509Zbc2}0e0~aS0P0p0V2b0P202F7z0waq0H9@a@3U8Ybf7u040H0O6v0@9Ua=7Yb68b0T8la?bI6Da_av0R4_a|aya~5p4_b1az7?bT3P0fb(889$3V0~al1(9^6/6;b:278b0I0N8~bwau9m3i5bbU9v7i5a256Sc29dc0b%b)8Cb80e8w8/b69Pb?7E9K8Ocgb+9DbCbE2x1fbz0_8kb{bOa^6M925taxc76W5rbZbW5E5raH3Mb)cNcc8Nbbcn8+8g040Scj0_8L8NbH3rb*cTb,8p8%6*cu8D0~bM4watbQb~3j6X33a}9r5E6Qc6aD9w5p5F9fcMcNd6c%8H04b.bvcy3U7F0Yc-9D0t0#9~0L0%c-bybw5#0~cWdq4+bKcx9i4yb}0L5E7ec`bVc|6P7kc b25+7r3pd7b(cPbB1WcR9.8:dscX84clc#3Rd8dr9E8?c,du8ac/dx6h9jcAbR5,cDd0c3d?cHdG3j7(5:dOd6dQ0VdTc$9/b-2adX8586e58`04b_e99KcfdUche7b/d+27dfdhb-2udo0~0J0Te90~0Cebd#e6c*0A7~80dcdyb+b^eqcVet040Nc:4bb|c?dB6P94dEcE5}c57meY7?0u94d e0dOdQ2F7 0qd!2Ld$4+0i0S0~0o3Xa6d.77d:7ocB9oeXd^9d0u9tdJb!d29ydNcb83b8e.80e;7CdVdae8cSde6;eAe=8Cb^b`bN6y0Z6B6i6w6k6t1h0z6nfE2S2N0taX2M6l750)0+0-0Q04.
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.

Indice 2

On pourra compléter le code

Python
1
2
3
4
5
6
7
8
9
def est_bien_parenthesee(expression):
    pile = ...
    for c in ...:
        if c in ...:
            pile.append(...)
        elif c in fermant:
            if ... or ... != ouverture[c]:
                return False
    return pile == ...