In diesem Lernprogramm erfahren Sie, wie Sie in Python nach gültigen Klammern suchen.
Bei einer Reihe von Klammern ist die Überprüfung, ob die Klammerkombination gültig ist, eine beliebte Frage in einem Codierungsinterview. Und in den nächsten Minuten werden Sie die Technik zur Lösung dieser Frage lernen und auch eine Python-Funktion codieren, um eine bestimmte Zeichenfolge zu validieren.
Inhaltsverzeichnis
Was ist das gültige Klammerproblem?
Beginnen wir unsere Diskussion mit der Beantwortung der Frage: Was ist das Problem der gültigen Klammern?
Gegeben ist eine Zeichenfolge, die die Zeichen einfache Klammern, geschweifte und eckige Klammern enthält: () [] {}, müssen Sie überprüfen, ob die angegebene Klammerkombination gültig ist oder nicht.
Eine gültige Klammerzeichenfolge erfüllt die folgenden beiden Bedingungen:
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 Stack ist eine LIFO-Datenstruktur (Last In First Out), in der Sie Elemente an die Spitze des Stacks hinzufügen und sie auch von der Spitze des Stacks entfernen können.
Wenn Sie dem Stack-Top ein Element hinzufügen, führen Sie einen Push-Vorgang durch, wenn Sie ein Element vom Stack-Top entfernen, führen Sie einen Pop-Vorgang durch.
Wir verwenden die folgenden beiden 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.
So prüfen Sie auf gültige Klammern
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 eine gerade Anzahl von Zeichen enthalten. 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: Überqueren Sie die Saite von links nach rechts. Nennen wir den String test_str und die einzelnen Zeichen im String char.
Schritt 2: Wenn das erste Zeichen char eine öffnende Klammer ist (, {, or [, push it to the top of the stack and proceed to the next character in the string.
Step 3: Now, check if the next character (char) is an opening or a closing bracket.
Step 3.1: If it’s an opening bracket, push it again onto the stack.
Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.
Step 4: Here again, there are 3 possibilities based on the value popped off the stack:
Step 4.1: If is an opening bracket of the same type, loop back to step 3.
Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.
Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.
Valid Parentheses String Examples Walkthrough
Now let’s take three examples and walk through the above steps.
📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.
#1. As a first example, let test_str = “{()”.
- { is the first character, and it’s an opening bracket, so you push it to the stack.
- The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
- The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
- At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.
#2. In this second example, let test_str = “()]”
- Das erste Zeichen ( ist eine öffnende Klammer; schieben Sie es auf den Stapel.
- Das zweite Zeichen ) 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 Stapel leer – was bedeutet, dass es keine passende öffnende Klammer gibt [. Hence, this string is invalid.
#3. In this final example, test_str = “{()}”.
- The first two characters {( are opening brackets, so push them onto the stack.
- The third character is a closing ), so pop off the stack top – (.
- The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
- After you have traversed the entire string, the stack is empty and test_str is valid! ✅
📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!
In the next section, let’s see how to translate our concept to Python code.
Python Program to Check for Valid Parentheses
In Python, you can use the list to emulate a stack.
You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.
The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.
So you now know how to implement the push and pop operations on a Python list, emulating the stack.
As a next step, let’s answer the question: how to differentiate between opening and closing brackets?
Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]‘, ‚)‘ als Werte. Sie können die Methode .keys() verwenden, um auf einzelne Schlüssel im Wörterbuch 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 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 können help(is_valid) oder is_valid.__doc__ verwenden, um den Docstring 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 prüft, ob die Zeichenfolge in Klammern gültig ist, und funktioniert wie folgt.
- Die Funktion is_valid übernimmt einen Parameter, test_str, der die zu validierende Zeichenfolge in Klammern ist. Es gibt True oder False zurück, je nachdem, ob die Zeichenfolge test_str gültig ist oder nicht.
- Stack ist hier die Python-Liste, die den Stack emuliert.
- Und par_dict ist das Python-Wörterbuch mit öffnenden Klammern als Schlüssel und schließenden Klammern als entsprechenden Werten.
- Wenn wir beim Durchlaufen der Zeichenfolge auf eine Bedingung stoßen, die die Zeichenfolge in Klammern ungültig macht, gibt die Funktion False zurück und wird beendet.
- Nachdem Sie alle Zeichen in der Zeichenfolge durchlaufen haben, stapeln Sie == [] überprüft, 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 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 kennengelernt, bei dem der Stack als bevorzugte Datenstruktur verwendet wurde.
- Anschließend haben Sie gelernt, wie Sie eine Klammerkombination mithilfe eines Python-Wörterbuchs validieren: mit öffnenden Klammern, den Schlüsseln und den entsprechenden schließenden Klammern als Werten.
- 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 im Online-Python-Editor von wdzwdz zu codieren. Fühlen Sie sich frei, diese Anleitung erneut zu lesen, wenn Sie Hilfe benötigen!
Sehen Sie sich weitere Python-Tutorials an. Viel Spaß beim Programmieren!🎉