În acest tutorial, veți învăța să verificați pentru paranteze valide în Python.
Având în vedere un șir de paranteze, verificarea dacă combinația de paranteze este validă este o întrebare populară la interviu de codificare. Și în următoarele câteva minute, veți învăța tehnica de a rezolva această întrebare și, de asemenea, veți codifica o funcție Python pentru a valida un șir dat.
Cuprins
Care este problema parantezelor valide?
Să începem discuția prin a răspunde la întrebarea, care este problema parantezelor valide?
Dat un șir care conține caracterele paranteze simple, acolade și acolade pătrate: () [] {}, trebuie să verificați dacă combinația de paranteze dată este validă sau nu.
Un șir de paranteze valid îndeplinește următoarele două condiții:
Iată câteva exemple de șiruri de paranteze valide și invalide.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
În abordarea noastră de rezolvare a problemelor, stiva este structura de date care va juca un rol esențial. Să revizuim elementele de bază ale unei stive în secțiunea următoare.
Structura de date a stivei revizuită
Stiva este o structură de date ultimul intrat, primul ieșit (LIFO), în care puteți adăuga elemente în partea de sus a stivei și, de asemenea, le puteți elimina din partea de sus a stivei.
Când adăugați un element în partea de sus a stivei, efectuați o operație de împingere, când eliminați un element din partea de sus a stivei, efectuați o operațiune de pop.
Vom folosi următoarele două reguli pentru a veni cu un set de operații pe care le putem efectua pe șirul de paranteze.
- Împingeți toate suporturile de deschidere pe stivă.
- Dacă întâlniți un suport de închidere, scoateți partea de sus a stivei.
Să trecem la rezolvarea problemei de verificare a parantezelor valide.
Cum să verificați dacă există paranteze valide
Punând cap la cap toate observațiile din exemplele de mai sus, avem următoarele.
Verificați lungimea șirului de paranteze: dacă este impar, șirul este invalid
Deoarece fiecare paranteză de deschidere trebuie să aibă o paranteză de închidere, un șir valid ar trebui să conțină un număr par de caractere. Dacă lungimea șirului este impară, puteți concluziona imediat că are o combinație nevalidă de paranteze.
# 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 = "{())}"
În continuare, să vedem cum putem aborda când numărul de caractere din șir este par
Lungimea șirului de paranteze este egală: ce urmează?
Pasul 1: Traversați șirul de la stânga la dreapta. Să numim șirul test_str și caracterele individuale din șirul char.
Pasul 2: Dacă primul caracter este o paranteză de deschidere (, {, sau [, 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 = “()]”
- Primul caracter ( este o paranteză de deschidere; împingeți-l în stivă.
- Al doilea caracter ) este o paranteză de închidere; ieșiți din partea de sus a stivei, care se întâmplă să fie ) – un suport de deschidere de același tip. Treceți la următorul caracter.
- Al treilea caracter ]este o paranteză pătrată de închidere și ar trebui să ieși din nou din partea de sus a stivei. Cu toate acestea, după cum puteți vedea, stiva este goală, ceea ce înseamnă că nu există un suport de deschidere potrivit [. 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 ‘}’, ‘]’, ‘)’ ca valori. Puteți folosi metoda .keys() pentru a accesa chei individuale în dicționar.
Să folosim tot ce am învățat pentru a scrie definiția funcției is_valid().
Înțelegerea definiției funcției
Citiți următoarea celulă de cod care conține definiția funcției. Puteți vedea că am folosit pașii din diagramă în tandem cu explicația de mai sus.
În plus, am adăugat și un docstring inclusiv:
- o scurtă descriere a funcției
- argumentele din apelul funcției
- valorile returnate din funcție
▶ Puteți utiliza help(is_valid) sau is_valid.__doc__ pentru a prelua documentul.
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 == []
Funcția Python is_valid verifică dacă șirul de paranteze este valid și funcționează după cum urmează.
- Funcția is_valid preia un parametru, test_str, care este șirul de paranteze care trebuie validat. Returnează True sau False, în funcție de dacă șirul test_str este valid sau nu.
- Aici, stiva este lista Python care emulează stiva.
- Și par_dict este dicționarul Python, cu paranteze de deschidere ca taste și paranteze de închidere ca valori corespunzătoare.
- În timpul parcurgerii șirului, dacă ne confruntăm cu orice condiție care face ca șirul din paranteze să fie invalid, funcția returnează False și iese.
- După ce parcurgeți toate caracterele din șir, stivuiți == [] verifică dacă stiva este goală. Dacă da, test_str este valid, iar funcția returnează True. În caz contrar, funcția returnează False.
Acum, să mergem mai departe și să facem câteva apeluri de funcție pentru a verifica dacă funcția noastră funcționează corect.
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
Din fragmentul de cod de mai sus, putem concluziona că funcția funcționează conform așteptărilor!
Concluzie 🧑💻
Iată un rezumat rapid a ceea ce ați învățat.
- În primul rând, ați fost introdus în problema verificării parantezelor valide.
- Apoi, ați învățat o abordare pentru a rezolva problema folosind stiva ca structură de date de alegere.
- Apoi ați învățat cum să validați o combinație de paranteze folosind un dicționar Python: cu paranteze de deschidere, chei și paranteze de închidere corespunzătoare ca valori.
- În cele din urmă, ați definit funcția Python pentru a verifica dacă un anumit șir de paranteze este valid.
Ca pas următor, încercați să codificați problema în editorul online Python al tipstrick.ro. Simțiți-vă liber să revedeți acest ghid dacă aveți nevoie de ajutor!
Consultați mai multe tutoriale Python. Codare fericită!🎉