So prüfen Sie in Python auf gültige Klammern

In diesem Tutorial lernen Sie es auf gültige Klammern prüfen bei Python.

Bei einer Reihe von Klammern prüfen, ob die Klammerkombination ist gültig ist eine beliebte Programmierfrage in Vorstellungsgesprächen. Und in den nächsten Minuten lernen Sie die Technik zur Lösung dieser Frage kennen und programmieren auch a Python-Funktion um eine gegebene Zeichenkette zu validieren.

What is the Valid Parentheses Problem?

Beginnen wir unsere Diskussion mit der Beantwortung der Frage: Was ist das gültige Klammerproblem?

Gegeben ist eine Zeichenfolge, die die Zeichen einfache Klammern, geschweifte und enthält quadratisch Zahnspange: () [] {}, müssen Sie überprüfen, ob die angegebene Klammerkombination gültig ist oder nicht.

Eine gültige Klammerzeichenfolge erfüllt die folgenden beiden Bedingungen:

Jede öffnende Klammer muss ein haben Abstimmung schließende Klammer des gleichen Typs.
Die Klammern sollten in der geschlossen werden und beseitigen Muskelschwäche Ordnung.

Hier sind einige Beispiele für gültige und ungültige Klammerzeichenfolgen.

test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

In unserem Problemlösungsansatz ist der Stack die Datenstruktur, die eine zentrale Rolle spielt. Sehen wir uns im nächsten Abschnitt die Grundlagen eines Stacks an.

Die Stack-Datenstruktur neu aufgelegt

Der Stapel ist a zuletzt rein, zuerst raus (LIFO)-Datenstruktur, in der Sie Elemente an die Spitze des Stapels hinzufügen und auch von der Spitze des Stapels entfernen können.

Wenn Sie hinzufügen ein Element auf die Stapelspitze, führen Sie a drücken Betrieb, wenn Sie entfernene ein Element aus dem Stapel oben, führen Sie a Pop Erfassung sind.

Wir verwenden die folgenden zwei Regeln, um eine Reihe von Operationen zu erstellen, die wir an der Zeichenfolge in Klammern ausführen können.

Schieben Sie alle öffnenden Klammern auf den Stapel.
Wenn Sie auf eine schließende Klammer stoßen, entfernen Sie die Stapeloberseite.

Fahren wir fort, um das Problem der Überprüfung gültiger Klammern zu lösen.

How to Check for Valid Parentheses

Wenn wir alle Beobachtungen aus den obigen Beispielen zusammenfassen, haben wir Folgendes.

Überprüfen Sie die Länge der Zeichenfolge in Klammern: Wenn sie ungerade ist, ist die Zeichenfolge ungültig

Da jede öffnende Klammer eine schließende Klammer haben muss, sollte ein gültiger String ein enthalten sogar Anzahl von Charakteren. Wenn die Länge der Zeichenfolge ungerade ist, können Sie sofort schließen, dass sie eine ungültige Kombination von Klammern enthält.

# 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 = "{())}"

Sehen wir uns als Nächstes an, wie wir vorgehen können, wenn die Anzahl der Zeichen in der Zeichenfolge gerade ist

Die Länge der Zeichenfolge in Klammern ist gerade: was kommt als nächstes?

Schritt 1: Durchlaufe die Saite von links nach rechts. Nennen wir die Zeichenfolge test_str, und die einzelnen Zeichen in der Zeichenfolge char.

Schritt 2: Wenn das erste Zeichen char ist eine öffnende Klammer (, {bezeichnet, oder [, verschieben Sie es an die Spitze des Stapels und fahren Sie mit dem nächsten Zeichen in der Zeichenfolge fort.

Schritt 3: Prüfen Sie nun, ob das nächste Zeichen (char) ist eine öffnende oder schließende Klammer.

Schritt 3.1: Wenn es sich um eine öffnende Klammer handelt, schieben Sie sie erneut auf den Stapel.

Schritt 3.2: Wenn Sie stattdessen auf eine schließende Klammer stoßen, lösen Sie die Stapelspitze und fahren Sie mit Schritt 4 fort.

Schritt 4: Auch hier gibt es 3 Möglichkeiten, basierend auf dem vom Stack gepoppten Wert:

Schritt 4.1: If ist eine öffnende Klammer des gleich eingeben, zurück zu Schritt 3.

Schritt 4.2: Wenn es sich um eine öffnende Klammer von a handelt anders Typ, können Sie wiederum schlussfolgern, dass es sich nicht um eine gültige Klammerzeichenfolge handelt.

Schritt 4.3: Die letzte Möglichkeit ist, dass der Stapel ist leer. Auch dies ist der Fall einer ungültigen Zeichenfolge, da Sie auf eine schließende Klammer gestoßen sind, die keine passende öffnende Klammer hat.

Valid Parentheses String Examples Walkthrough

Nehmen wir nun drei Beispiele und gehen die obigen Schritte durch.

📑 Wenn Sie bereits wissen, wie das funktioniert, können Sie gerne zum nächsten Abschnitt springen.

#1. Lassen Sie als erstes Beispiel test_str = "{()".

{ ist das erste Zeichen, und es ist eine öffnende Klammer, also schieben Sie es auf den Stapel.
Das nächste Zeichen ( ist auch eine öffnende Klammer, also schieben Sie es auch auf den Stapel.
Das dritte Zeichen in der Zeichenfolge ) ist eine schließende Klammer, also müssen Sie den Stack-Top entfernen, der (.
An diesem Punkt haben Sie das Ende der Zeichenfolge erreicht. Aber der Stack enthält immer noch die Öffnung { , die nie geschlossen wurde. Also die in Klammern angegebene Zeichenfolge test_str ist ungültig.

#2. Lassen Sie in diesem zweiten Beispiel test_str = "()]"

Der erste Charakter ( ist eine öffnende Klammer; schieben Sie es auf den Stapel.
Der zweite Charakter ) ist eine schließende Klammer; Pop off the stack top, was zufällig ) ist – eine öffnende Klammer des gleichen Typs. Fahren Sie mit dem nächsten Zeichen fort.
Das dritte Zeichen ] ist eine schließende eckige Klammer, und Sie sollten wieder von der Stapelspitze abspringen. Wie Sie jedoch sehen können, ist der Stack leer– was bedeutet, dass es keine passende öffnende Klammer gibt [. Daher ist diese Zeichenfolge ungültig.

#3. In diesem letzten Beispiel test_str = "{()}".

Die ersten beiden Zeichen {( öffnende Klammern, schieben Sie sie also auf den Stapel.
Das dritte Zeichen ist ein Abschluss ), also knallen Sie die Stapelspitze ab – (.
Das nächste Zeichen } ist eine schließende geschweifte Klammer, und wenn Sie die Stapeloberseite öffnen, erhalten Sie { – eine öffnende geschweifte Klammer.
Nachdem Sie die gesamte Zeichenfolge durchlaufen haben, ist der Stapel leer und test_str ist gültig! ✅

📌 Ich habe das folgende Flussdiagramm zusammengestellt, das die Schritte im Problem der Überprüfung gültiger Klammern umreißt. Sie können es zum schnellen Nachschlagen speichern!

Im nächsten Abschnitt sehen wir uns an, wie wir unser Konzept in Python-Code übersetzen.

Python Program to Check for Valid Parentheses

In Python können Sie die Liste verwenden, um einen Stack zu emulieren.

Sie können die Verwendung .append() -Methode, um Elemente am Ende der Liste hinzuzufügen. Dies ähnelt dem Schieben an die Spitze des Stapels.

Dieses .pop() -Methode gibt das letzte Element aus der Liste zurück, und dies ähnelt dem Abheben von der Spitze des Stapels – um das zuletzt hinzugefügte Element zu entfernen.

Sie wissen jetzt also, wie Sie die Push- und Pop-Operationen in einer Python-Liste implementieren und den Stack emulieren.

Als nächsten Schritt beantworten wir die Frage: Wie kann man zwischen öffnenden und schließenden Klammern unterscheiden?

Nun, Sie können ein Python-Wörterbuch verwenden – mit den öffnenden Klammern '{', '[', '(' wie die Tasten des Wörterbuchs und die entsprechenden schließenden Klammern '}', ']', ')' wie die Werte. Du kannst den ... benutzen .keys() Methode, um auf einzelne Schlüssel im Wörterbuch zuzugreifen.

Lassen Sie uns alles, was wir gelernt haben, verwenden, um die Definition von zu schreiben is_valid() Funktion.

Verständnis der Funktionsdefinition

Lesen Sie die folgende Codezelle mit der Funktionsdefinition durch. Sie können sehen, dass wir die Schritte im Flussdiagramm zusammen mit der obigen Erklärung verwendet haben.

Darüber hinaus haben wir auch eine hinzugefügt Dokumentzeichenfolge einschließlich:

eine kurze Beschreibung der Funktion
die Argumente im Funktionsaufruf
die Rückgabewerte der Funktion

▶ Sie dürfen verwenden help(is_valid) or is_valid.__doc__ um den Dokumentstring abzurufen.

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 == []

Die Python-Funktion is_valid überprüft, ob die Zeichenfolge in Klammern gültig ist, und funktioniert wie folgt.

Die Funktion is_valid nimmt einen Parameter auf, test_str Dies ist die Klammerzeichenfolge, die validiert werden soll. Es kehrt zurück True or False je nachdem, ob die Zeichenfolge oder nicht test_str ist gültig.
Hier stack ist die Python-Liste, die den Stack emuliert.
Und par_dict ist das Python-Wörterbuch, mit öffnenden Klammern als Tasten und schließende Klammern als entsprechende Werte.
Wenn wir beim Durchlaufen der Zeichenfolge auf eine Bedingung stoßen, die die Zeichenfolge in Klammern ungültig macht, kehrt die Funktion zurück False und geht.
Nachdem alle Zeichen in der Zeichenfolge durchlaufen wurden, stack == [] prüft ob stack is leer. Falls ja, test_str gültig ist und die Funktion zurückkehrt True. Andernfalls kehrt die Funktion zurück False.

Lassen Sie uns nun fortfahren und ein paar Funktionsaufrufe durchführen, um zu überprüfen, ob unsere Funktion ordnungsgemäß funktioniert.

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

Aus dem obigen Codeausschnitt können wir schließen, dass die Funktion wie erwartet funktioniert!

Fazit

Hier ist eine kurze Zusammenfassung dessen, was Sie gelernt haben.

Zuerst wurden Sie in das Problem der Prüfung auf gültige Klammern eingeführt.
Als Nächstes haben Sie einen Ansatz zur Lösung des Problems mithilfe von erlernt Stapel als Datenstruktur der Wahl.
Anschließend haben Sie gelernt, wie Sie eine Klammerkombination mithilfe eines Python-Wörterbuchs validieren: mit öffnenden Klammern, der Tasten, und die entsprechenden schließenden Klammern als Werte.
Schließlich haben Sie die Python-Funktion definiert, um zu prüfen, ob eine bestimmte Zeichenfolge in Klammern gültig ist.

Versuchen Sie als nächsten Schritt, das Problem zu codieren Der Online-Python-Editor von Geekflare. Fühlen Sie sich frei, diese Anleitung erneut zu lesen, wenn Sie Hilfe benötigen!

Check out more Python-Tutorials. Viel Spaß beim Codieren!