Comment vérifier les parenthèses valides en Python

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 !

organigramme python entre parenthèses valides

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 revient True or False selon que la chaîne ou non test_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 si stack is vide. Si oui, test_str est valide et la fonction renvoie True. Sinon, la fonction retourne False.

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 !