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['>']
'<'

###

∞/∞

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

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 == ...