Comment vérifier la validité des parenthèses en Python

Dans ce tutoriel, vous apprendrez à vérifier la validité des parenthèses en Python.

Étant donné une chaîne de parenthèses, vérifiez si la combinaison de parenthèses est valide est une question d'entretien de codage populaire. Au cours des prochaines minutes, vous apprendrez la technique pour résoudre cette question et vous coderez également une fonction Python pour valider une chaîne donnée.

Qu'est-ce que le problème des parenthèses valides ?

Commençons par répondre à la question suivante : qu'est-ce que le problème des parenthèses valides ?

Étant donné une chaîne de caractères contenant des parenthèses simples, des accolades et des crochets : () [] {}, vous devez vérifier si la combinaison de parenthèses donnée est valide ou non.

Une chaîne de parenthèses valide satisfait aux deux conditions suivantes :

1. Chaque parenthèse ouvrante doit avoir une parenthèse fermante correspondant du même type.
2. Les parenthèses doivent être fermées dans le bon ordre.

Voici quelques exemples de chaînes de parenthèses valides et non valides.

test_str = "{}]" -->
 INVALIDE, ] n'a jamais été ouvert
test_str = "[{}]" -->
 VALIDE
test_str = "[]" -->
 VALIDE
test_str = "[]{}" -->
 VALIDE
test_str = "[{]}" -->
 INVALIDE, les parenthèses sont mal fermées !

Dans notre approche de la résolution de problèmes, la pile est la structure de données qui jouera un rôle central. Passons en revue les principes de base d'une pile dans la section suivante.

Réexamen de la structure de données de la pile

La pile est une structure de données LIFO ( dernier entré premier sorti ), dans laquelle vous pouvez ajouter des éléments au sommet de la pile et en retirer.

Lorsque vous ajoutez un élément au sommet de la pile, vous effectuez une opération "pousser", et lorsque vous retraiteun élément du sommet de la pile, vous effectuez une opération "pop".

Nous allons utiliser les deux règles suivantes pour trouver un ensemble d'opérations que nous pouvons effectuer sur la chaîne de parenthèses.

• Poussez toutes les parenthèses ouvrantes sur la pile.
• Si vous rencontrez une parenthèse fermante, retirez-la du sommet de la pile.

Passons maintenant à la résolution du problème de vérification de la validité des parenthèses.

Comment vérifier la validité des parenthèses

En rassemblant toutes les observations tirées des exemples ci-dessus, nous obtenons les résultats suivants.

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

Comme chaque parenthèse ouvrante doit être accompagnée d'une parenthèse fermante, une chaîne de caractères valide doit contenir un nombre paire de caractères. Si la longueur de la chaîne est impaire, vous pouvez conclure immédiatement que la combinaison de parenthèses n'est pas valide.

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

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

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

Ensuite, voyons comment nous pouvons résoudre le problème lorsque le nombre de caractères de la chaîne est pair

La longueur de la chaîne de caractères entre parenthèses est paire : que faire ensuite ?

Étape 1 : Parcourez 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 char est une parenthèse ouvrante (, {, ou [, placez-le en haut de la pile et passez au caractère suivant de la chaîne.

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

Étape 3.1 : S'il s'agit d'un crochet ouvrant, repoussez-le sur la pile.

Étape 3.2 : Si vous rencontrez une parenthèse fermante, retirez-la du haut de la pile et passez à l'étape 4.

Étape 4 : Ici encore, il y a trois possibilités 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, revenez à l'étape 3.

Étape 4.2: S'il s'agit d'une parenthèse ouvrante d'un type différent, vous pouvez à nouveau conclure qu'il ne s'agit pas d'une chaîne de parenthèses valide.

Étape 4.3 : La dernière possibilité est que la pile soit vide. Là encore, il s'agit d'une chaîne non valide, car vous avez rencontré une parenthèse fermante qui n'a pas de parenthèse ouvrante correspondante.

Exemples de chaînes de parenthèses valides Walkthrough

Prenons maintenant trois exemples et passons en revue les étapes ci-dessus.

si vous avez déjà compris comment cela fonctionne, n'hésitez pas à passer à la section suivante.

#1. Comme premier exemple, laissez test_str = "{()".

• { est le premier caractère, et c'est un crochet ouvrant, donc vous le poussez sur la pile.
• Le caractère suivant ( est également une parenthèse ouvrante, alors allez-y et poussez-le également sur la pile.
• Le troisième caractère de la chaîne ) est une parenthèse fermante, vous devez donc l'extraire du sommet de la pile, ce qui renvoie à (.
• À ce stade, vous avez atteint la fin de la chaîne. Mais la pile contient toujours le caractère d'ouverture { , qui n'a jamais été fermé. La chaîne de caractères entre parenthèses test_str n'est donc pas valide.

#2. Dans ce deuxième exemple, laissez test_str = "()]"

• Le premier caractère ( est une parenthèse ouvrante ; poussez-le sur la pile.
• Le deuxième caractère ) est une parenthèse fermante ; retirez le sommet de la pile, qui se trouve être ) - une parenthèse ouvrante du même type. Passez au caractère suivant.
• Le troisième caractère ] est un crochet fermant, et vous devez à nouveau retirer le sommet de la pile. Cependant, comme vous pouvez le voir, la pile est vide, ce quisignifie qu'il n'y a pas de crochet ouvrant correspondant [. Par conséquent, cette chaîne n'est pas valide.

#3. Dans ce dernier exemple, test_str = "{()}".

• Les deux premiers caractères {( sont des parenthèses ouvrantes, il faut donc les placer sur la pile.
• Le troisième caractère est un ) fermant, donc retirez le haut de la pile - (.
• Le caractère suivant } est une accolade fermante, et lorsque vous retirez le sommet de la pile, vous obtenez { - une accolade ouvrante.
• Après avoir parcouru toute la chaîne, la pile est vide et test_str est valide ! ✅

📌 J'ai créé l'organigramme suivant qui décrit les étapes du problème de vérification de la validité des parenthèses. Vous pouvez le conserver pour vous y référer rapidement !

Dans la section suivante, nous verrons comment traduire notre concept en code Python.

Programme Python pour vérifier la validité des parenthèses

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

Vous pouvez utiliser la méthode .append() pour ajouter des éléments à la fin de la liste. Cette opération est similaire à l'ajout d'éléments au sommet de la pile.

La méthode .pop( ) renvoie le dernier élément de la liste, ce qui est similaire à l'extraction du sommet de la pile - pour supprimer le dernier élément ajouté.

Vous savez maintenant comment mettre en œuvre les opérations push et pop sur une liste Python, en émulant la pile.

Dans une prochaine étape, répondons à la question suivante : comment différencier 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 à des clés individuelles du dictionnaire.

Utilisons tout ce que nous avons appris pour écrire la définition de la fonction is_valid().

Comprendre la définition de la fonction

Lisez la cellule de code suivante contenant la définition de la fonction. Vous pouvez voir que nous avons utilisé les étapes de l'organigramme en tandem avec l'explication ci-dessus.

En outre, nous avons également ajouté une chaîne de documentation comprenant

• une brève description de la fonction
• les arguments de l'appel de fonction
• les valeurs de retour de la fonction

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

def isValid(test_str) :
 '''Vérifier 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) is odd -> invalid !
 if len(test_str)%2 != 0 :
 return False
 # initialize parentheses dict
 par_dict = {'(':')','{':'}','[':']'}
 stack = []
 for char in test_str :
   # pousser le crochet d'ouverture sur la pile
 if char in par_dict.keys() :
 stack.append(char)
 else :
     # crochet fermant sans crochet ouvrant correspondant
 if stack == [] :
 return False
 # si crochet fermant -> pop stack top
 open_brac = stack.pop()
 # crochet ne correspondant pas -> 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 comme suit.

• La fonction is_valid prend un 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 émule la pile.
• Et par_dict est le dictionnaire Python, avec des parenthèses ouvrantes comme clés et des parenthèses fermantes comme valeurs correspondantes.
• En parcourant la chaîne, si nous rencontrons une condition qui rend la chaîne de parenthèses invalide, la fonction renvoie Faux et sort.
• 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. Dans le cas contraire, la fonction renvoie False.

Maintenant, procédons à quelques appels de fonction pour vérifier que notre fonction fonctionne correctement.

str1 = '{}[]'
isValid(str1)
# Sortie : True

str2 = '{((}'
isValid(str2)
# Output : False

str3 = '[{()}]'
isValid(str3)
# Output : True

str4 = '[{)}]'
isValid(str4)
# Output : False

str5 = '[[]}'
isValid(str5)
# Output : False

D'après l'extrait de code ci-dessus, nous pouvons conclure que la fonction fonctionne comme prévu !

Conclusion

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

• Tout d'abord, vous avez été initié au problème de la vérification de la validité des parenthèses.
• Ensuite, vous avez appris une approche pour résoudre le problème en utilisant la pile comme structure de données de choix.
• Vous avez ensuite appris à valider une combinaison de parenthèses à l'aide d'un dictionnaire Python : les parenthèses ouvrantes sont les clés et les parenthèses fermantes correspondantes sont les valeurs.
• Enfin, vous avez défini la fonction Python permettant de vérifier si une chaîne de parenthèses donnée est valide.

Dans une prochaine étape, essayez de coder le problème sur l'éditeur Python en ligne de Geekflare. N'hésitez pas à consulter à nouveau ce guide si vous avez besoin d'aide !

Consultez d'autres tutoriels Python. Bon codage !