In diesem Tutorial werden wir uns damit beschäftigen, wie man in Python die Gültigkeit von Klammerausdrücken überprüft.
Die Frage, ob eine gegebene Sequenz von Klammern korrekt geschlossen ist, ist ein häufiges Thema in Bewerbungsgesprächen für Programmierer. Innerhalb der nächsten Minuten werden Sie eine Methode erlernen, um diese Herausforderung zu meistern und eine Python-Funktion entwickeln, die eine Zeichenkette hinsichtlich ihrer Klammerstruktur validiert.
Was ist das Problem der gültigen Klammerung?
Beginnen wir mit der Klärung, was genau das Problem mit der Validierung von Klammern beinhaltet.
Gegeben sei eine Zeichenkette, die verschiedene Klammertypen enthält: runde Klammern (), geschweifte Klammern {} und eckige Klammern []. Ihre Aufgabe ist es zu überprüfen, ob die Anordnung der Klammern in dieser Zeichenkette korrekt ist.
Eine gültige Klammerzeichenkette muss zwei Hauptbedingungen erfüllen:
- Jede öffnende Klammer muss eine passende schließende Klammer desselben Typs haben.
- Die schließenden Klammern müssen in der korrekten Reihenfolge erscheinen.
Hier sind einige Beispiele, die verdeutlichen, was eine gültige bzw. ungültige Klammerstruktur ausmacht:
test_str = "{}]" --> UNGÜLTIG, ] wurde nie geöffnet
test_str = "[{}]" --> GÜLTIG
test_str = "[]" --> GÜLTIG
test_str = "[]{}" --> GÜLTIG
test_str = "[{]}" --> UNGÜLTIG, Klammern falsch geschlossen!
Bei der Lösung dieses Problems spielt die Datenstruktur Stack eine entscheidende Rolle. Im nächsten Abschnitt werden wir uns die Grundlagen eines Stacks genauer ansehen.
Die Stack-Datenstruktur im Überblick
Ein Stack ist eine LIFO-Datenstruktur (Last In First Out). Das bedeutet, dass Elemente, die zuerst hinzugefügt wurden, zuletzt wieder entfernt werden. Neue Elemente werden immer oben auf den Stack gelegt und von dort auch wieder entfernt.
Das Hinzufügen eines Elements zum Stack wird als Push-Operation bezeichnet, während das Entfernen eines Elements als Pop-Operation bekannt ist.
Um Klammerausdrücke zu analysieren, verwenden wir folgende zwei grundlegende Regeln:
- Alle öffnenden Klammern werden auf den Stack gelegt.
- Wenn eine schließende Klammer gefunden wird, wird das oberste Element vom Stack entfernt.
Lassen Sie uns nun fortfahren und eine Lösung für das Problem der gültigen Klammerprüfung entwickeln.
So überprüfen Sie gültige Klammern
Wenn wir alle Beobachtungen aus den vorherigen Beispielen zusammenfassen, kommen wir zu folgenden Schlüssen.
Prüfen Sie die Länge der Klammerzeichenkette: Bei ungerader Länge ist die Zeichenkette ungültig
Da jede öffnende Klammer eine entsprechende schließende Klammer benötigt, sollte eine gültige Zeichenkette eine gerade Anzahl von Zeichen aufweisen. Wenn die Länge der Zeichenkette ungerade ist, können wir sie als ungültig einstufen.
# len(test_str) = 3 (ungerade); ] hat keine öffnende [
test_str = "{}]"
# len(test_str) = 3 (ungerade); ( hat keine schließende )
test_str = "[(]"
# len(test_str) = 5 (ungerade); es gibt ein überflüssiges )
test_str = "{())}"
Als Nächstes sehen wir uns an, wie wir vorgehen können, wenn die Anzahl der Zeichen in der Zeichenkette gerade ist.
Die Länge der Klammerzeichenkette ist gerade: Wie geht es weiter?
Schritt 1: Durchlaufen Sie die Zeichenkette von links nach rechts. Wir nennen die Zeichenkette test_str und die einzelnen Zeichen char.
Schritt 2: Wenn das aktuelle Zeichen char eine öffnende Klammer ist (, { oder [, dann legen wir es auf den Stack und gehen zum nächsten Zeichen in der Zeichenkette über.
Schritt 3: Nun prüfen wir, ob das nächste Zeichen (char) eine öffnende oder schließende Klammer ist.
Schritt 3.1: Ist es eine öffnende Klammer, legen wir sie ebenfalls auf den Stack.
Schritt 3.2: Wenn wir stattdessen auf eine schließende Klammer stoßen, entfernen wir das oberste Element vom Stack und gehen zu Schritt 4 über.
Schritt 4: Hier gibt es wieder drei Möglichkeiten, basierend auf dem Wert, der vom Stack entfernt wurde:
Schritt 4.1: Wenn es eine öffnende Klammer des gleichen Typs ist, gehen wir zurück zu Schritt 3.
Schritt 4.2: Wenn es sich um eine öffnende Klammer eines anderen Typs handelt, können wir schließen, dass die Zeichenkette keine gültige Klammerstruktur hat.
Schritt 4.3: Die letzte Möglichkeit ist, dass der Stack leer ist. Auch dies ist ein Fall einer ungültigen Zeichenkette, da wir auf eine schließende Klammer gestoßen sind, für die keine passende öffnende Klammer existiert.
Beispiele für gültige Klammerzeichenketten
Betrachten wir nun drei Beispiele und gehen die oben genannten Schritte durch.
📑 Wenn Sie bereits verstanden haben, wie das funktioniert, können Sie gerne zum nächsten Abschnitt springen.
#1. Als erstes Beispiel nehmen wir an, test_str = “{()”.
- { ist das erste Zeichen und eine öffnende Klammer, also legen wir es auf den Stack.
- Das nächste Zeichen ( ist ebenfalls eine öffnende Klammer, also legen wir es ebenfalls auf den Stack.
- Das dritte Zeichen in der Zeichenkette ) ist eine schließende Klammer, also entfernen wir das oberste Element vom Stack, was ( ergibt.
- An diesem Punkt haben wir das Ende der Zeichenkette erreicht. Der Stack enthält jedoch noch die öffnende { , die nie geschlossen wurde. Daher ist die gegebene Klammerzeichenkette test_str ungültig.
#2. In diesem zweiten Beispiel sei test_str = “()]”
- Das erste Zeichen ( ist eine öffnende Klammer; legen Sie sie auf den Stapel.
- Das zweite Zeichen ) ist eine schließende Klammer; Entfernen Sie das oberste Element vom Stack, das 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 wir müssten das oberste Element vom Stack entfernen. Wie wir sehen können, ist der Stack jedoch leer – was bedeutet, dass keine passende öffnende Klammer [ vorhanden ist. Daher ist diese Zeichenkette ungültig.
#3. In diesem letzten Beispiel ist test_str = “{()}”.
- Die ersten beiden Zeichen {( sind öffnende Klammern, also legen wir sie auf den Stack.
- Das dritte Zeichen ist ein schließendes ), also entfernen wir das oberste Element vom Stack – (.
- Das nächste Zeichen } ist eine schließende geschweifte Klammer, und wenn wir das oberste Element vom Stack entfernen, erhalten wir { – eine öffnende geschweifte Klammer.
- Nachdem wir die gesamte Zeichenkette durchlaufen haben, ist der Stack leer und test_str ist gültig! ✅
📌 Ich habe das folgende Flussdiagramm erstellt, das die Schritte zur Überprüfung gültiger Klammern zusammenfasst. Sie können es als schnelle Referenz speichern!
Im nächsten Abschnitt sehen wir uns an, wie wir unser Konzept in Python-Code umsetzen können.
Python-Programm zur Überprüfung gültiger Klammern
In Python können Sie eine Liste verwenden, um einen Stack nachzubilden.
Sie können die Methode .append() verwenden, um Elemente am Ende der Liste hinzuzufügen. Dies ist analog zum Ablegen auf den Stack.
Die Methode .pop() gibt das letzte Element der Liste zurück, und dies entspricht dem Entfernen des obersten Elements vom Stack – um das zuletzt hinzugefügte Element zu entfernen.
Sie wissen nun also, wie Sie die Push- und Pop-Operationen auf einer Python-Liste implementieren, um einen Stack zu simulieren.
Als nächsten Schritt beantworten wir die Frage: Wie unterscheidet man zwischen öffnenden und schließenden Klammern?
Nun, Sie können ein Python-Dictionary verwenden – mit den öffnenden Klammern ‚{‚, ‚[‚ und ‚(‚ als Schlüsseln des Dictionary und den entsprechenden schließenden Klammern ‚}‘, ‚]‘ und ‚)‘ als Werten. Sie können die Methode .keys() verwenden, um auf einzelne Schlüssel im Dictionary zuzugreifen.
Lassen Sie uns alles, was wir gelernt haben, verwenden, um die Definition der Funktion is_valid() zu schreiben.
Verständnis der Funktionsdefinition
Lesen Sie den folgenden Codeblock mit der Funktionsdefinition. Sie werden sehen, dass wir die Schritte im Flussdiagramm zusammen mit der obigen Erklärung angewendet haben.
Darüber hinaus haben wir auch einen Docstring hinzugefügt, der Folgendes umfasst:
- eine kurze Beschreibung der Funktion
- die Argumente im Funktionsaufruf
- die Rückgabewerte der Funktion
▶ Sie können help(is_valid) oder is_valid.__doc__ verwenden, um den Docstring abzurufen.
def isValid(test_str):
'''Prüft, ob eine gegebene Klammerzeichenkette gültig ist.
Args:
test_str (str): Die zu validierende Klammerzeichenkette
Returns:
True, wenn test_str gültig ist; ansonsten False
'''
# len(test_str) ist ungerade -> ungültig!
if len(test_str)%2 != 0:
return False
# Initialisiere das Klammer-Dictionary
par_dict = {'(':')','{':'}','[':']'}
stack = []
for char in test_str:
# Öffnende Klammer auf den Stack legen
if char in par_dict.keys():
stack.append(char)
else:
# Schließende Klammer ohne passende öffnende Klammer
if stack == []:
return False
# Wenn schließende Klammer -> oberstes Element vom Stack entfernen
open_brac = stack.pop()
# Nicht passende Klammer -> ungültig!
if char != par_dict[open_brac]:
return False
return stack == []
Die Python-Funktion is_valid prüft, ob die Klammerzeichenkette gültig ist, und funktioniert wie folgt:
- Die Funktion is_valid übernimmt einen Parameter, test_str, der die zu validierende Klammerzeichenkette ist. Sie gibt True oder False zurück, je nachdem, ob die Zeichenkette test_str gültig ist oder nicht.
- Stack ist hier die Python-Liste, die den Stack simuliert.
- Und par_dict ist das Python-Dictionary mit öffnenden Klammern als Schlüsseln und schließenden Klammern als entsprechenden Werten.
- Wenn wir beim Durchlaufen der Zeichenkette auf eine Bedingung stoßen, die die Klammerzeichenkette ungültig macht, gibt die Funktion False zurück und wird beendet.
- Nachdem Sie alle Zeichen in der Zeichenkette durchlaufen haben, überprüft stack == [], ob der Stack leer ist. Wenn ja, ist test_str gültig und die Funktion gibt True zurück. Andernfalls gibt die Funktion False zurück.
Lassen Sie uns nun ein paar Funktionsaufrufe durchführen, um zu überprüfen, ob unsere Funktion wie erwartet funktioniert.
str1 = '{}[]'
isValid(str1)
# Ausgabe: True
str2 = '{((}'
isValid(str2)
# Ausgabe: False
str3 = '[{()}]'
isValid(str3)
# Ausgabe: True
str4 = '[{)}]'
isValid(str4)
# Ausgabe: False
str5 = '[[]}'
isValid(str5)
# Ausgabe: 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 haben Sie das Problem der Überprüfung von Klammern kennengelernt.
- Als Nächstes haben Sie einen Ansatz zur Lösung des Problems kennengelernt, bei dem der Stack als bevorzugte Datenstruktur verwendet wurde.
- Anschließend haben Sie gelernt, wie Sie eine Klammerkombination mithilfe eines Python-Dictionaries validieren: mit öffnenden Klammern, den Schlüsseln und den entsprechenden schließenden Klammern als Werten.
- Schließlich haben Sie eine Python-Funktion definiert, um zu prüfen, ob eine bestimmte Klammerzeichenkette gültig ist.
Versuchen Sie als nächsten Schritt, das Problem im Online-Python-Editor von wdzwdz zu codieren. Wenn Sie Hilfe benötigen, können Sie dieses Tutorial gerne erneut lesen!
Sehen Sie sich weitere Python-Tutorials an. Viel Spaß beim Programmieren! 🎉