Parenthésage correct⚓︎

On dispose de chaînes de caractères contenant uniquement :

des parenthèses ouvrantes '(' et fermantes ')',
des crochets ouvrants '[' et fermants ']',
des accolades ouvrantes '{' et fermantes '}'.

On appellera délimiteur une parenthèse, un crochet ou une accolade. Un parenthésage est correct si :

pour chaque délimiteur le nombre de fermants coïncide avec le nombre d'ouvrants,
en parcourant la chaîne de gauche à droite, pour chaque délimiteur, le nombre d'ouvrant est à tout moment supérieur ou égal au nombre de fermants,
les différents délimiteurs ne s'entre-croisent pas, par exemple '[(])' est incorrect.

On souhaite programmer une fonction est_bien_parenthesee qui prend en paramètre une chaîne de délimiteurs expression et renvoie True ou False selon qu'elle est correctement parenthésée ou non.

On adopte la démarche suivante utilisant une Pile :

on parcourt les caractères de la chaîne,
si le caractère lu est un délimiteur ouvrant on l'empile,
si c'est un délimiteur fermant :
- si la pile est vide, on renvoie False,
- sinon, si le caractère dépilé n'est pas le délimiteur ouvrant du caractère lu, on renvoie False,
à la fin du parcours, si la pile est vide on renvoie True, sinon False.

On utilise un dictionnaire pour associer facilement délimiteurs fermants et ouvrants.

La classe Pile est fournie ci-dessous. Elle est déjà "chargée" en mémoire et donc utilisable sans import dans la zone de saisie.

Classe Pile (pour information)

🐍 Script Python

class Pile:
  "Classe définissant une structure de pile"

  def __init__(self):
      self.contenu = []

  def est_vide(self):
      "Renvoie le booléen True si la pile est vide, False sinon"
      return self.contenu == []

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

  def depile(self):
      """
      Retire et renvoie l'élément placé au sommet de la pile,
      si la pile n'est pas vide
      """
      if not self.est_vide():
          return self.contenu.pop()

Exemples

🐍 Console Python

>>> est_bien_parenthesee('([()[]]{()})')
True
>>> est_bien_parenthesee('{}[(])')
False
>>> est_bien_parenthesee('[][')
False
>>> est_bien_parenthesee('[]]')
False

∞/∞

#--- HDR ---#bksl-nlclass Pile:bksl-nl "Classe définissant une structure de pile"bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = []bksl-nlbksl-nl def estpy-undvide(self):bksl-nl "Renvoie le booléen True si la pile est vide, False sinon"bksl-nl return self.contenu == []bksl-nlbksl-nl def empile(self, v):bksl-nl "Place l'élément v au sommet de la pile"bksl-nl self.contenu.append(v)bksl-nlbksl-nl def depile(self):bksl-nl """bksl-nl Retire et renvoie l'élément placé au sommet de la pile,bksl-nl si la pile n'est pas videbksl-nl """bksl-nl if not self.estpy-undvide():bksl-nl return self.contenu.pop()bksl-nl#--- HDR ---#bksl-nlbksl-nldef estpy-undbienpy-undparenthesee(expression):bksl-nl ouvrants = {')': '(',bksl-nl ...bksl-nl }bksl-nlbksl-nl pile = Pile()bksl-nl for delimeteur in expression:bksl-nl if delimeteur in "([{":bksl-nl pile.empile(...)bksl-nl else:bksl-nl if ...:bksl-nl return ...bksl-nl elif pile.depile() != ...:bksl-nl return ...bksl-nlbksl-nl return pile....bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert estpy-undbienpy-undparenthesee('([()[]]{()})')bksl-nlassert not estpy-undbienpy-undparenthesee('{}[(])')bksl-nlassert not estpy-undbienpy-undparenthesee('[][')bksl-nlassert not estpy-undbienpy-undparenthesee('[]]')bksl-nlbksl-nl# --- HDR ---#bksl-nlclass Pile:bksl-nl "Classe définissant une structure de pile"bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = []bksl-nlbksl-nl def estpy-undvide(self):bksl-nl "Renvoie le booléen True si la pile est vide, False sinon"bksl-nl return self.contenu == []bksl-nlbksl-nl def empile(self, v):bksl-nl "Place l'élément v au sommet de la pile"bksl-nl self.contenu.append(v)bksl-nlbksl-nl def depile(self):bksl-nl """bksl-nl Retire et renvoie l'élément placé au sommet de la pile,bksl-nl si la pile n'est pas videbksl-nl """bksl-nl if not self.estpy-undvide():bksl-nl return self.contenu.pop()bksl-nlbksl-nlbksl-nl# --- HDR ---#bksl-nlbksl-nlbksl-nldef estpy-undbienpy-undparenthesee(expression):bksl-nl ouvrants = {")": "(", "]": "[", "}": "{"}bksl-nlbksl-nl pile = Pile()bksl-nl for delimiteur in expression:bksl-nl if delimiteur in "([{":bksl-nl pile.empile(delimiteur)bksl-nl else:bksl-nl if pile.estpy-undvide():bksl-nl return Falsebksl-nl elif pile.depile() != ouvrants[delimiteur]:bksl-nl return Falsebksl-nlbksl-nl return pile.estpy-undvide()bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert estpy-undbienpy-undparenthesee("([()[]]{()})")bksl-nlassert not estpy-undbienpy-undparenthesee("{}[(])")bksl-nlassert not estpy-undbienpy-undparenthesee("[][")bksl-nlassert not estpy-undbienpy-undparenthesee("[]]")bksl-nlbksl-nl

Commentaires⚓︎

On suit la démarche décrite dans l'énoncé. Pour chaque caractère (délimiteur) de la chaîne :

si c'est un délimiteur ouvrant (if delimiteur in "([{":), on l'empile,
sinon :
- on vérifie que la pile est non-vide (si elle l'est on renvoie False),
- on vérifie que le délimiteur au sommet de la pile correspond à celui lu. Si ce n'est pas le cas, on renvoie False,
en fin de parcours, l'expression est bien parenthésée si la pile est vide : on renvoie simplement le résultat de pile.est_vide().