Dans ce didacticiel, vous apprendrez à vérifier les parenthèses valides en Python.
Étant donné une chaîne de parenthèses, vérifier si la combinaison de parenthèses est Info de contact. est une question d'entretien de codage populaire. Et au cours des prochaines minutes, vous apprendrez la technique pour résoudre cette question et également coder un fonction Python pour valider une chaîne donnée.
What is the Valid Parentheses Problem?
Commençons notre discussion en répondant à la question, quel est le problème des parenthèses valides ?
Soit une chaîne contenant les caractères parenthèses simples, bouclé et carré croisillons:
() [] {}
, vous devez vérifier si la combinaison de parenthèses donnée est valide ou non.
Une chaîne de parenthèses valide satisfait les deux conditions suivantes :
- Chaque parenthèse d'ouverture doit avoir un assorti parenthèse fermante du même type.
- Les parenthèses doivent être fermées dans le correct ordre.
Voici quelques exemples de chaînes de parenthèses valides et non valides.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
Dans notre approche de résolution de problèmes, la pile est la structure de données qui jouera un rôle central. Passons en revue les bases d'une pile dans la section suivante.
La structure de données de la pile revisitée
La pile est un dernier entré, premier sorti (LIFO) structure de données, où vous pouvez ajouter des éléments en haut de la pile et également les supprimer du haut de la pile.
Lorsque vous ajouter un élément au sommet de la pile, vous effectuez une pousser opération, lorsque vous supprimere un élément du sommet de la pile, vous effectuez une pop fonctionnement.
Nous utiliserons les deux règles suivantes pour proposer un ensemble d'opérations que nous pouvons effectuer sur la chaîne entre parenthèses.
- Poussez tous les supports d'ouverture sur la pile.
- Si vous rencontrez une parenthèse fermante, retirez le haut de la pile.
Passons à la résolution du problème de vérification des parenthèses valides.
How to Check for Valid Parentheses
En rassemblant toutes les observations des exemples ci-dessus, nous avons ce qui suit.
Vérifiez la longueur de la chaîne entre parenthèses : si elle est impaire, la chaîne est invalide
Comme chaque parenthèse ouvrante doit avoir une parenthèse fermante, une chaîne valide doit contenir un pair nombre de caractères. Si la longueur de la chaîne est impaire, vous pouvez en conclure immédiatement qu'elle contient une combinaison de parenthèses non valide.
# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"
# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"
# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"
Ensuite, voyons comment nous pouvons nous attaquer lorsque le nombre de caractères dans la chaîne est pair
La longueur de la chaîne entre parenthèses est paire : et ensuite ?
Étape 1 : Traversez la corde 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 [, poussez-le vers le haut de la pile et passez au caractère suivant de la chaîne.
Étape 3 : Maintenant, vérifiez si le caractère suivant (char
) est une parenthèse ouvrante ou fermante.
Étape 3.1 : S'il s'agit d'un support d'ouverture, poussez-le à nouveau sur la pile.
Étape 3.2 : Si vous rencontrez un crochet de fermeture à la place, retirez le haut de la pile et passez à l'étape 4.
Étape 4 : Là encore, il y a 3 possibilités basées sur la valeur sortie de la pile :
Étape 4.1 : Si est 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 différent type, 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. Encore une fois, c'est le cas d'une chaîne non valide, car vous avez rencontré une parenthèse fermante qui n'a pas de parenthèse ouvrante correspondante.
Valid Parentheses String Examples Walkthrough
Prenons maintenant trois exemples et parcourons 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, laissons test_str = "{()"
.
{
est le premier caractère, et c'est un crochet ouvrant, donc vous le poussez vers la pile.- Le caractère suivant ( est également un crochet ouvrant, 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 sortir du haut de la pile, ce qui renvoie (.
- À ce stade, vous avez atteint la fin de la chaîne. Mais la pile contient toujours l'ouverture { , qui n'a jamais été fermée. Ainsi, la chaîne de parenthèses donnée
test_str
est invalide.

#2. Dans ce deuxième exemple, soit test_str = "()]"
- Le premier personnage
(
est une parenthèse ouvrante ; poussez-le vers la pile. - Le deuxième personnage
)
est une parenthèse fermante ; pop du haut de la pile, qui se trouve être ) - un crochet d'ouverture du même type. Passez au caractère suivant. - Le troisième personnage
]
est un crochet fermant, et vous devriez à nouveau sortir du haut de la pile. Cependant, comme vous pouvez le voir, la pile est vide- ce qui signifie qu'il n'y a pas de support d'ouverture correspondant[
. Par conséquent, cette chaîne n'est pas valide.

#3. Dans ce dernier exemple, test_str = "{()}"
.
- Les deux premiers personnages
{(
ouvrent des crochets, alors poussez-les sur la pile. - Le troisième caractère est une fermeture
)
, alors sortez du haut de la pile -(
. - Le personnage suivant
}
est une accolade fermante, et quand vous sautez le haut de la pile, vous obtenez{
– une accolade ouvrante. - Après avoir traversé toute la chaîne, la pile est vide et
test_str
est valable! ✅

📌 J'ai rassemblé l'organigramme suivant décrivant les étapes du problème de vérification des parenthèses valides. Vous pouvez l'enregistrer pour référence rapide !

Dans la section suivante, voyons comment traduire notre concept en code Python.
Python Program to Check for Valid Parentheses
En Python, vous pouvez utiliser la liste pour émuler une pile.
Vous pouvez utiliser le .append()
méthode pour ajouter des éléments à la fin de la liste. Cela revient à pousser vers le haut de la pile.
, .pop()
La méthode renvoie le dernier élément de la liste, et cela est similaire à la sortie du haut de la pile - pour supprimer le dernier élément ajouté.

Vous savez donc maintenant comment implémenter les opérations push et pop sur une liste Python, en émulant la pile.
Dans une prochaine étape, répondons à la question : comment différencier les parenthèses ouvrantes et fermantes ?
Eh bien, vous pouvez utiliser un dictionnaire Python - avec les crochets ouvrants '{', '[', '('
car clés du dictionnaire et les parenthèses fermantes correspondantes '}', ']', ')'
comme les valeurs. Vous pouvez utiliser le .keys()
méthode pour accéder à des clés individuelles dans le dictionnaire.
Utilisons tout ce que nous avons appris pour écrire la définition du is_valid()
la fonction.
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 parallèle avec l'explication ci-dessus.
De plus, nous avons également ajouté un chaîne de documentation comprenant:
- une brève description de la fonction
- les arguments dans l'appel de la fonction
- les valeurs de retour de la fonction
▶ Vous pouvez utiliser help(is_valid)
or is_valid.__doc__
pour récupérer la docstring.
def isValid(test_str):
'''Check if a given parentheses string is valid.
Args:
test_str (str): The parentheses string to be validated
Returns:
True if test_str is valid; else 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:
# push opening bracket to stack
if char in par_dict.keys():
stack.append(char)
else:
# closing bracket without matching opening bracket
if stack == []:
return False
# if closing bracket -> pop stack top
open_brac = stack.pop()
# not matching bracket -> invalid!
if char != par_dict[open_brac]:
return False
return stack == []
La fonction Python is_valid
vérifie si la chaîne entre parenthèses est valide et fonctionne comme suit.
- La fonction
is_valid
prend en un paramètre,test_str
qui est la chaîne de parenthèses à valider. Il revientTrue
orFalse
selon que la chaîne ou nontest_str
est valable. - 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 les parenthèses fermantes comme correspondant valeurs. - Lors de la traversée de la chaîne, si nous rencontrons une condition qui rend la chaîne entre parenthèses invalide, la fonction renvoie
False
et sort. - Après avoir traversé tous les caractères de la chaîne,
stack == []
vérifie sistack
is vide. Si oui,test_str
est valide et la fonction renvoieTrue
. Sinon, la fonction retourneFalse
.
Maintenant, continuons et effectuons quelques appels de fonction pour vérifier que notre fonction fonctionne correctement.
str1 = '{}[]'
isValid(str1)
# Output: True
str2 = '{((}'
isValid(str2)
# Output: False
str3 = '[{()}]'
isValid(str3)
# Output: True
str4 = '[{)}]'
isValid(str4)
# Output: False
str5 = '[[]}'
isValid(str5)
# Output: False
À partir de l'extrait de code ci-dessus, nous pouvons conclure que la fonction fonctionne comme prévu !
Conclusion
Voici un bref résumé de ce que vous avez appris.
- Tout d'abord, vous avez été initié au problème de la vérification des parenthèses valides.
- Ensuite, vous avez appris une approche pour résoudre le problème en utilisant empiler comme structure de données de choix.
- Vous avez ensuite appris à valider une combinaison de parenthèses à l'aide d'un dictionnaire Python : avec des parenthèses ouvrantes, le clés, et les parenthèses fermantes correspondantes comme valeurs.
- Enfin, vous avez défini la fonction Python pour 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 à revisiter ce guide si vous avez besoin d'aide !
Regardez plus de Tutoriels Python. Bon codage !