Solution de Bon parenthésage - Sujet 08 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Écrire la fonction maximum_tableau, prenant en paramètre un tableau non vide de nombres tab (de type list) et renvoyant le plus grand élément de ce tableau.

Exemples :

>>> maximum_tableau([98, 12, 104, 23, 131, 9])
131
>>> maximum_tableau([-27, 24, -3, 15])
24

Exercice 2

EXERCICE 2 (10 points)

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 :

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []

    def empiler(self, v):
        """Place l'élément v au sommet de la pile"""
        self.contenu.append(v)

    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n’est pas vide. Produit une erreur sinon.
        """
        assert not self.est_vide()
        return self.contenu.pop()

On souhaite programmer une fonction bon_parenthesage qui prend en paramètre une chaîne de caractères ch formée de parenthèses et renvoie True si la chaîne est bien parenthésée et False 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.

Compléter le code de la fonction bon_parenthesage ci-dessous:

def bon_parenthesage(ch):
    """Renvoie un booléen indiquant si la chaîne ch
    est bien parenthésée"""
    p = Pile()
    for c in ch:
        if c == ...:
            p.empiler(c)
        elif c == ...:
            if p.est_vide():
                ...
            else:
                ...
    return ...

Exemples :

>>> bon_parenthesage("((()())(()))")
True
>>> bon_parenthesage("())(()")
False
>>> bon_parenthesage("(())(()")
False

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• tab est de type list et n’est jamais vide : 1 <= len(tab) <= 10^4
• tab ne contient que des nombres entiers
• -10^6 <= tab[i] <= 10^6
• tab n’est pas nécessairement trié

Exercice 2

Contraintes :

• ch est de type str et 0 <= len(ch) <= 10^4
• ch ne contient que les caractères ( et )
• la chaîne vide est un parenthésage correct

Exercice 1 - le maximum d’un tableau

L’idée. On ne peut pas connaître le plus grand élément sans avoir regardé tout le tableau. On le parcourt donc une seule fois, en gardant dans une variable la plus grande valeur rencontrée jusqu’ici. À chaque nouvel élément, on compare : s’il est plus grand que ce qu’on avait, il devient le nouveau maximum. Comme le tableau n’est jamais vide, on peut partir de son premier élément.

Un exemple. Pour [98, 12, 104, 23, 131, 9] : on part de 98, puis 12 ne change rien, 104 devient le maximum, 23 ne change rien, 131 devient le maximum, 9 ne change rien. On renvoie 131.

def maximum_tableau(tab):
    maximum = tab[0]
    # tab n'est jamais vide : on part du premier element, jamais d'une valeur inventee
    for i in range(1, len(tab)):
        if tab[i] > maximum:
            maximum = tab[i]
    return maximum

maximum contient toujours le plus grand élément parmi ceux déjà vus. La boucle commence à l’indice 1 parce que l’élément d’indice 0 sert de valeur de départ : le comparer à lui-même ne servirait à rien. Partir de 0 comme valeur initiale serait une erreur, car le deuxième exemple [-27, 24, -3, 15] contient des nombres négatifs.

Exercice 2 - le bon parenthésage

L’idée. On lit la chaîne de gauche à droite avec une pile qui mémorise les parenthèses ouvertes et pas encore refermées. Chaque ( rencontrée est empilée. Chaque ) doit refermer une ouvrante : on dépile. Deux choses seulement peuvent mal se passer : on tombe sur une ) alors que la pile est vide (elle ne referme rien), ou bien il reste des parenthèses dans la pile à la fin (elles n’ont jamais été refermées).

Un exemple. Pour "())(()" : ( empile, ) dépile, la pile est vide, puis arrive une ) alors qu’il n’y a plus rien à dépiler. On renvoie False tout de suite.

def bon_parenthesage(ch):
    """Renvoie un booléen indiquant si la chaîne ch
    est bien parenthésée"""
    p = Pile()
    for c in ch:
        if c == "(":
            p.empiler(c)
        elif c == ")":
            if p.est_vide():
                # une fermante sans ouvrante en attente : rien ne pourra la rattraper
                return False
            else:
                p.depiler()
    # il reste des ouvrantes dans la pile si elles n'ont pas toutes ete refermees
    return p.est_vide()

La hauteur de la pile, c’est le nombre de parenthèses ouvertes en attente. Le return False dans le cas de la pile vide sort immédiatement de la fonction : une fois qu’une fermante est en trop, la suite de la chaîne ne peut plus rien réparer. Il faut aussi le return p.est_vide() de la fin, sinon "(())(()" passerait : on n’y trouve jamais de fermante en trop, mais deux ouvrantes restent dans la pile. Enfin, la chaîne vide donne une pile vide, donc True, ce qui est bien le résultat attendu.