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-nlouvrant = "([{<"bksl-nlfermant = ")]}>"bksl-nlouverture = {f: o for o, f in zip(ouvrant, fermant)}bksl-nlbksl-nldef estpy-undbienpy-undparenthesee(expression):bksl-nl pile = []bksl-nl for c in expression:bksl-nl if c in ouvrant:bksl-nl pile.append(c)bksl-nl elif c in fermant:bksl-nl if pile == [] or pile.pop() != ouverture[c]:bksl-nl return Falsebksl-nl return pile == []bksl-nlbksl-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-nl

Il y a plusieurs façons de construire le dictionnaire des ouvertures associées aux fermetures.

La version codée en dur qui n'est pas généralisable.

🐍 Script Python

ouverture = {')': '(', ']': '[', '}': '{', '>': '<'}

La première avec boucle :

🐍 Script Python

ouvrant = "([{<"
fermant = ")]}>"
ouverture = {}  # dictionnaire vide
for i in range(len(fermant)):
    ouverture[fermant[i]] = ouvrant[i]

La seconde par compréhension :

🐍 Script Python

ouvrant = "([{<"
fermant = ")]}>"
ouverture = {fermant[i]: ouvrant[i] for i in range(len(fermant))}

Sans les indices, avec un style fonctionnel, on zippe un élément de fermant avec celui associé de ouvrant, dans le même ordre.

🐍 Script Python

ouvrant = "([{<"
fermant = ")]}>"
ouverture = {f: o for f, o in zip(fermant, ouvrant)}

Ou bien en échangeant le rôle de fermant et ouvrant dans le zip, comme dans le corrigé tout en haut.

Enfin, il est même possible d'écrire

🐍 Script Python

ouverture = dict(zip(fermant, ouvrant))

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