Parenthésage

On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.

Un parenthésage est correct si :

  • le nombre de parenthèses ouvrantes de la chaĂ®ne est Ă©gal au nombre de parenthèses fermantes.
  • en parcourant la chaĂ®ne de gauche Ă  droite, le nombre de parenthèses dĂ©jĂ  ouvertes doit ĂŞtre, Ă  tout moment, supĂ©rieur ou Ă©gal au nombre de parenthèses dĂ©jĂ  fermĂ©es.

Ainsi, ((()())(())) est un parenthésage correct.

Les parenthésages ())(() et (())(() sont, eux, incorrects.

On dispose du code de la classe Pile suivant :

Python
class Pile:
    """ Classe définissant une pile """
    def __init__(self):
        self.valeurs = []

    def est_vide(self):
        """Renvoie True si la pile est vide, False sinon"""
        return self.valeurs == []

    def empiler(self, c):
        """Place l’élément c au sommet de la pile"""
        self.valeurs.append(c)

    def depiler(self):
        """Supprime l’élément placé au sommet de la pile, à condition qu’elle soit non vide"""
        if self.est_vide() == False:
            self.valeurs.pop()

On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne de caractères chaine formée de parenthèses et renvoie True si la chaîne est bien parenthésée etFalse sinon.

Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve une parenthèse fermante, on dépile (si possible) la parenthèse ouvrante stockée au sommet de la pile.

La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.

Elle est, par contre, mal parenthésée :

  • si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide ;
  • ou si, Ă  la fin du parcours, la pile n’est pas vide.

Exemple

Python Console Session
>>> parenthesage("((()())(()))")
True
>>> parenthesage("())(()")
False
>>> parenthesage("(())(()")
False
Compléter le code de la fonction parenthesage.

###(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

.128013kg: r);S/q(.loF4y6b=ac15ud3t28_Pw7evp-fh0T9mnRis050A0J0C0v0V0n0W0e0w0n0v0W0W0u010C0V0L010406050W0z0S0S0v0f0r040i0o0n0z0;0o0T050j0{0}0 110_0L04051h1a1k0j1h0_0A0V0K0)0+0-0/0+0T0c0z0v0c0J0M0L0r0C0O180e0O0V0c0O0n1M0O0C0@050!0t0n0J1t0,0.011L1N1P1N0C1V1X1T0C0f1i1H0)140W0L0v0T0/0D011Z1v010N0$0J0T0v0S0J1T1^1`1 1#221X25270@0a0e0G0f0o0L0o0W0V170T0e0Y1?0f0f0J0w2s1a2a0T1i0j1H2F1/1;1:1U0A2c1w0V0T242p1T1q1s0*1!2P2R0T0o2V1T0L2y1i2D2F2,0`1_2t2X202#0f0~0n1T0v1K2y0N0/030F0F0w2$0J1P2!0o0M0D0M0x0@0e0x1a0v2-2:0^2/2b2=1#2@2_2{2}0J2 01313335372S3a3a3e0D3h3j1`3l2D2O013q0v2`1i2|0O2~3032340Y3A2#3C0B3e0B3G2C3k0_3K3o0/3N3P053R3T3w3V3z2Q3B3b0q3e0q3(1b3*3m2;1u3p0o2^3O3s3S3u3U3y3X3`3Z3b0y3e0y402,3+2:3L3/4a3?3x3W364g393b0s3e0s4m423,453.473r3Q3t3v4u3_383C0I3e0I4D3I4o3n4G3M4I494K4b4M3^4f4P3b0E3e0E4U2E4W442Y4Z483:3=4c3@4e4w4+0M0R3e0R4:3J4p3-4^4J3;4L4d4v3Y4y3c0P0@0x0P554=4q4!4`5c4}5e4x3C0x3d045w5m435o4_4s4|4N4*3{3c1}5y3F0j3i3)4V5B584r4$4t4)4 5I0x3#5y3%5N3H4;5R4Y5T5b4%5d4O5Y3}5y3 5%5P2E1l2*1a2V2I0A1;2N584v2U1r1i2)0J2+3k5_1i4v6a2b0V0A0/322D5v3s6h6j4~5f6m0e2g0J6p5t505x3(4F4@0b0@0Y0N6c0e5*4@0T0N0@1_2y0T1H0J0W1B0J6c6J200?040l6W6B2?0@0w0O0#2R6$574Y6Z0g0d6c0_413I5B6o016k2:3C5K5b6|5W6r3b1}6t266v6}6q5u761T5^6%1#0H3e0e7l6.4X4@0W0A0@020k0z0o0C0h7t7v7x7z7w0h6@7n2t730F6l3b5!726i7b6x5I3#78276w5:4h0M7M7g6/7p7r047l7l0U240K0o0V1Y0Q0f0z1Y2q0)6+3`0e6S0C0e0t7/2t6O246R0W0J1Y0Z0e0p3O860e2q2#196_5)8i6f7H7O6~1`3C5=7N7V5H7X3}7T7a747d0M8r7!7o207q7k7l7C7B7u7D8J7E8k6^2.3K7I7K0M4j4K7I7Q7X4j8x8t5X8!7f3i7)6I7h3.6N6H6X1#0o0@0u8;8.3M0@0G237G3L6Z0l0g7F8k6{8n7J6 4z6n988Z5g4A8$7P7W9f8*7(7)8=0/6D040N478`7#6(040w0 0v2A0J2y9u8E8?7j042Q9E4?9w6*6,6V968{6Z6?8P908T9a0M4R8X9d9j4Q1~6u8%759Y9l8,8,9o019q0V6G8k8-9v3p6)9z9B9D9^9:8@040u8_a08{0W5K8N0l8N90589S958R4p9W8p4,9c9*8A4-9h8z504-2F8+9.aw9:0T8:9Q9`0/a20mad5+0@0J0S0L230faG4@92aO9M9}0C9C9Pah9F0/6;ag6b8S988U529!an5052aq7ca-9-aw9_aY9;aI1P9@2,a@9L9{9xaTaV9K3La2a4b458a87s8L7x0gacaBa^af9Ubg8m6p8U5kam9i8u5gboa/9e5v5iau9ma?9n8{9=a|3ka~4qaAaXa aD0@aFbkbH047}0F0K6haWa$aC01926=a#6`a%bm9X5wbpar5Y3dbu9$3bb*bybAbA9:9q2y0C0z0f8ha}b_0w0@8b0%bV5QbOaj0T5v712|8Yb:5J9(79a,5Y715%b@bBbX9q3686aR1#bi4n9Va(b)7Mcd9#br5v7S9)bq8(bs7Zavcn9/8{az040LctbL04bNbJbP0YaL1XaNbOae0@93b#5`b%7bbn8rcBcj7X0x8wcGb,c=8CcLbG58b`0Zb}b bFaybIbWa^aEcS8|bQ0W0CbSbUd9bZc*2F6e5{695}661a0C60dp2L2G0v1Wdm0j5~6^0Y0!0$0W04.