Comment vérifier les parenthèses valides en Python

Dans ce tutoriel, vous allez acquérir la compétence de contrôler la validité des parenthèses dans un code Python.

Étant donné une séquence de parenthèses, déterminer si leur agencement est correct est un défi courant dans les entretiens techniques. Au cours des prochaines minutes, vous apprendrez une méthode pour résoudre cette problématique et développer une fonction Python capable de confirmer la validité d’une chaîne donnée.

En quoi consiste le problème des parenthèses valides ?

Pour démarrer, éclaircissons ce que signifie précisément le problème des parenthèses valides.

Considérez une chaîne contenant des parenthèses simples, des accolades et des crochets : (), [], {}. Le défi consiste à déterminer si l’arrangement de ces parenthèses est correct ou non.

Une chaîne de parenthèses est considérée comme valide si elle respecte les deux règles suivantes :

Chaque parenthèse ouvrante doit avoir une parenthèse fermante correspondante du même type.
Les parenthèses doivent se fermer dans l’ordre approprié.

Voici quelques exemples de chaînes de parenthèses qui sont soit valides, soit invalides.

test_str = "{}]" --> INVALIDE, la parenthèse ] n'a jamais été ouverte
test_str = "[{}]" --> VALIDE
test_str = "[]" --> VALIDE
test_str = "[]{}" --> VALIDE
test_str = "[{]}" --> INVALIDE, les crochets ne sont pas fermés correctement!

Notre approche pour résoudre ce problème repose sur l’utilisation d’une pile, une structure de données qui jouera un rôle essentiel. Examinons les principes de base d’une pile dans la section suivante.

Rappel sur la structure de données de la pile

La pile est une structure de données de type « dernier entré, premier sorti » (LIFO). On ajoute des éléments au sommet de la pile et on les retire également par le sommet.

L’ajout d’un élément au sommet de la pile est une opération « push », tandis que la suppression d’un élément au sommet est une opération « pop ».

Nous allons utiliser les deux règles suivantes pour définir les opérations que nous allons appliquer à notre chaîne de parenthèses.

Ajouter chaque parenthèse ouvrante à la pile.
Si l’on rencontre une parenthèse fermante, retirer l’élément du sommet de la pile.

Passons maintenant à la résolution concrète du problème de validation des parenthèses.

Comment vérifier la validité des parenthèses

En rassemblant les observations tirées des exemples précédents, nous pouvons dégager les conclusions suivantes.

Vérifier la longueur de la chaîne de parenthèses : Si elle est impaire, la chaîne est invalide

Étant donné que chaque parenthèse ouvrante doit avoir une contrepartie fermante, une chaîne valide doit contenir un nombre pair de caractères. Si la longueur de la chaîne est impaire, on peut immédiatement conclure que la combinaison de parenthèses est invalide.

# len(test_str) = 3 (impair); ] n'a pas de [ ouvrant
test_str = "{}]"

# len(test_str) = 3 (impair); ( n'a pas de ) fermante
test_str = "[(]"

# len(test_str) = 5 (impair); il y a un ) superflue
test_str = "{())}"

Voyons maintenant comment procéder lorsque le nombre de caractères de la chaîne est pair.

La longueur de la chaîne de parenthèses est paire : Que faire ensuite ?

Étape 1 : Parcourir la chaîne de gauche à droite. Appelons la chaîne test_str et les caractères individuels de la chaîne char.

Étape 2 : Si le premier caractère est une parenthèse ouvrante (, { ou [, l’ajouter au sommet de la pile et passer au caractère suivant dans la chaîne.

Étape 3 : Vérifier si le caractère suivant (char) est une parenthèse ouvrante ou fermante.

Étape 3.1 : S’il s’agit d’une parenthèse ouvrante, l’ajouter à nouveau à la pile.

Étape 3.2 : Si on rencontre une parenthèse fermante, retirer l’élément du sommet de la pile et passer à l’étape 4.

Étape 4 : Ici, trois cas de figure se présentent en fonction de la valeur retirée de la pile :

Étape 4.1 : S’il s’agit d’une parenthèse ouvrante du même type, retourner à l’étape 3.

Étape 4.2 : S’il s’agit d’une parenthèse ouvrante d’un type différent, on peut conclure que la chaîne n’est pas une chaîne de parenthèses valide.

Étape 4.3 : La dernière possibilité est que la pile soit vide. Dans ce cas également, la chaîne est invalide, car on rencontre une parenthèse fermante sans parenthèse ouvrante correspondante.

Exemples de parcours de chaînes de parenthèses valides

Examinons maintenant trois exemples concrets pour illustrer les étapes décrites ci-dessus.

📑 Si vous avez déjà bien compris le fonctionnement, n’hésitez pas à passer directement à la section suivante.

#1. Prenons comme premier exemple, test_str = « {() ».

{ est le premier caractère, et c’est une parenthèse ouvrante, on l’ajoute à la pile.
Le caractère suivant ( est également une parenthèse ouvrante, on l’ajoute donc à la pile.
Le troisième caractère de la chaîne ) est une parenthèse fermante, on doit donc retirer l’élément du sommet de la pile, qui est (.
À ce stade, on a parcouru toute la chaîne. Mais la pile contient toujours la parenthèse ouvrante { , qui n’a jamais été fermée. La chaîne de parenthèses test_str est donc invalide.

#2. Dans ce deuxième exemple, test_str = « ()] »

Le premier caractère ( est une parenthèse ouvrante ; on l’ajoute à la pile.
Le deuxième caractère ) est une parenthèse fermante ; on retire l’élément du sommet de la pile, qui se trouve être ( une parenthèse ouvrante du même type. On passe au caractère suivant.
Le troisième caractère ] est une parenthèse fermante, et il faudrait à nouveau retirer un élément du sommet de la pile. Cependant, la pile est vide, ce qui signifie qu’il n’y a pas de parenthèse ouvrante [ correspondante. Par conséquent, cette chaîne est invalide.

#3. Pour ce dernier exemple, test_str = « {()} ».

Les deux premiers caractères {( sont des parenthèses ouvrantes, on les ajoute donc à la pile.
Le troisième caractère est une parenthèse fermante ), on retire donc l’élément du sommet de la pile : (.
Le caractère suivant } est une accolade fermante, et lorsque l’on retire l’élément du sommet de la pile, on obtient { – une accolade ouvrante.
Après avoir parcouru toute la chaîne, la pile est vide et test_str est valide ! ✅

📌 Voici un organigramme qui récapitule les étapes de la résolution du problème de validation des parenthèses. Vous pouvez le sauvegarder pour référence rapide !

Dans la section suivante, nous allons voir comment traduire notre approche en code Python.

Programme Python pour valider les parenthèses

En Python, vous pouvez utiliser la liste pour simuler une pile.

Vous pouvez utiliser la méthode .append() pour ajouter des éléments à la fin de la liste. Cela correspond à l’ajout d’un élément au sommet de la pile.

La méthode .pop() renvoie le dernier élément de la liste, ce qui équivaut à retirer l’élément du sommet de la pile – pour supprimer le dernier élément ajouté.

Vous savez maintenant comment implémenter les opérations push et pop sur une liste Python, en simulant une pile.

L’étape suivante consiste à répondre à la question : comment faire la différence entre les parenthèses ouvrantes et fermantes ?

Vous pouvez utiliser un dictionnaire Python – avec les parenthèses ouvrantes ‘{‘, ‘[‘, ‘(‘ comme clés du dictionnaire et les parenthèses fermantes correspondantes ‘}’, ‘]’, ‘)’ comme valeurs. Vous pouvez utiliser la méthode .keys() pour accéder aux clés individuelles du dictionnaire.

Utilisons toutes ces connaissances pour écrire la définition de la fonction is_valid().

Comprendre la définition de la fonction

Lisez le code suivant qui contient la définition de la fonction. Vous remarquerez que nous avons suivi les étapes de l’organigramme tout en nous basant sur l’explication ci-dessus.

De plus, nous avons également ajouté une chaîne de documentation, qui inclut :

Une brève description de la fonction
Les arguments de l’appel de la fonction
Les valeurs renvoyées par la fonction

▶ Vous pouvez utiliser help(is_valid) ou is_valid.__doc__ pour récupérer la docstring.

def isValid(test_str):
  '''Vérifie si une chaîne de parenthèses donnée est valide.

  Args:
    test_str (str): La chaîne de parenthèses à valider
  
  Returns:
    True si test_str est valide ; sinon False 
  '''
  # len(test_str) est impaire -> invalide!
  if len(test_str)%2 != 0:
    return False
  # Initialiser le dictionnaire des parenthèses
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # Ajouter la parenthèse ouvrante à la pile
    if char in par_dict.keys():
      stack.append(char)
    else:
      # Parenthèse fermante sans parenthèse ouvrante correspondante
      if stack == []:
          return False
      # Si parenthèse fermante -> retirer l'élément du sommet de la pile
      open_brac = stack.pop()
      # Parenthèses non correspondantes -> invalide !
      if char != par_dict[open_brac]:
        return False
  return stack == []

La fonction Python is_valid vérifie si la chaîne de parenthèses est valide et fonctionne de la manière suivante.

La fonction is_valid prend en paramètre test_str, qui est la chaîne de parenthèses à valider. Elle renvoie True ou False selon que la chaîne test_str est valide ou non.
Ici, stack est la liste Python qui simule la pile.
Et par_dict est le dictionnaire Python, avec les parenthèses ouvrantes comme clés et les parenthèses fermantes correspondantes comme valeurs.
Lors du parcours de la chaîne, si l’on rencontre une condition qui rend la chaîne de parenthèses invalide, la fonction renvoie False et s’arrête.
Après avoir parcouru tous les caractères de la chaîne, stack == [] vérifie si la pile est vide. Si c’est le cas, test_str est valide et la fonction renvoie True. Sinon, la fonction renvoie False.

Effectuons maintenant quelques appels de fonction pour vérifier que notre fonction fonctionne correctement.

str1 = '{}[]'
isValid(str1)
# Résultat : True

str2 = '{((}'
isValid(str2)
# Résultat : False

str3 = '[{()}]'
isValid(str3)
# Résultat : True

str4 = '[{)}]'
isValid(str4)
# Résultat : False

str5 = '[[]}'
isValid(str5)
# Résultat : False

D’après l’extrait de code ci-dessus, on peut conclure que la fonction fonctionne comme prévu !

Conclusion 🧑‍💻

Voici un bref résumé de ce que vous avez appris.

Vous avez été initié au problème de la validation des parenthèses.
Vous avez découvert une approche pour résoudre ce problème en utilisant la pile comme structure de données.
Vous avez appris à valider une combinaison de parenthèses à l’aide d’un dictionnaire Python : en utilisant les parenthèses ouvrantes comme clés et les parenthèses fermantes correspondantes comme valeurs.
Enfin, vous avez créé une fonction Python pour vérifier si une chaîne de parenthèses donnée est valide.

Dans une prochaine étape, essayez de coder ce problème sur l’éditeur Python en ligne de toptips.fr. N’hésitez pas à revenir sur ce guide si vous avez besoin d’aide !

Découvrez d’autres tutoriels Python. Bon codage !🎉

0 Partages