Aller au contenu

Expression bien parenthésée (2)⚓︎

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

🐍 Console Python
>>> 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
🐍 Console Python
>>> 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.

🐍 Console Python
>>> ouverture['}']
'{'
>>> ouverture['>']
'<'
###
# testsbksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("(2 + 4)py-str7") == Truebksl-nlassert estpy-undbienpy-undparenthesee("tableau[f(i) - g(i)]") == Truebksl-nlassert estpy-undbienpy-undparenthesee(bksl-nl "int main(){int liste[2] = {4, 2}; return (10py-strliste[0] + liste[1]);}"bksl-nl) == Truebksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("(une parenthèse laissée ouverte") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("{<(}>)") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("c'est trop tard ;-)") == Falsebksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("a(b)c") == Truebksl-nlassert estpy-undbienpy-undparenthesee("a[]b") == Truebksl-nlassert estpy-undbienpy-undparenthesee("{ }") == Truebksl-nlassert estpy-undbienpy-undparenthesee("") == Truebksl-nlassert estpy-undbienpy-undparenthesee("()[]{}<>") == Truebksl-nlassert estpy-undbienpy-undparenthesee("([{<>}])") == Truebksl-nlassert estpy-undbienpy-undparenthesee("<{[([{<>}])]}>") == Truebksl-nlassert estpy-undbienpy-undparenthesee(bksl-nl "("py-str100 + "["py-str100 + "{"py-str100 + "<"py-str100bksl-nl + ">"py-str100 + "}"py-str100 + "]"py-str100 + ")"py-str100bksl-nl) == Truebksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("a(bc") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("a]b") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("} {") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("><") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("([)]{<}>") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("([{<}>)]") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("{<([[<{>}])]}>") == Falsebksl-nlassert estpy-undbienpy-undparenthesee(bksl-nl "("py-str100 + "["py-str100 + "{"py-str100 + "<"py-str100bksl-nl + "<(>)"bksl-nl + ">"py-str100 + "}"py-str100 + "]"py-str100 + ")"py-str100bksl-nl) == Falsebksl-nlbksl-nlbksl-nlbksl-nl ∞/∞

ouvrant = "([{<"bksl-nlfermant = ")]}>"bksl-nlouverture = { # dictionnaire qui donne l'ouvrant en fonction du fermantbksl-nl ')': '(',bksl-nl ']': '[',bksl-nl '}': '{',bksl-nl '>': '<',bksl-nl}bksl-nlbksl-nlbksl-nldef estpy-undbienpy-undparenthesee(expression):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("(2 + 4)py-str7") == Truebksl-nlassert estpy-undbienpy-undparenthesee("tableau[f(i) - g(i)]") == Truebksl-nlassert estpy-undbienpy-undparenthesee(bksl-nl "int main(){int liste[2] = {4, 2}; return (10py-strliste[0] + liste[1]);}"bksl-nl) == Truebksl-nlbksl-nlassert estpy-undbienpy-undparenthesee("(une parenthèse laissée ouverte") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("{<(}>)") == Falsebksl-nlassert estpy-undbienpy-undparenthesee("c'est trop tard ;-)") == Falsebksl-nlbksl-nlNone

A

Z

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

🐍 Script Python
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 == ...
Retour en haut de la page