Ebben az oktatóanyagban megtanulhatja, hogyan ellenőrizze a Pythonban érvényes zárójeleket.
Ha adott egy zárójelsor, a zárójelkombináció érvényességének ellenőrzése egy népszerű kódolási interjúkérdés. A következő néhány percben pedig megtanulja a kérdés megoldásának technikáját, valamint egy Python-függvényt is kódol egy adott karakterlánc érvényesítésére.
Tartalomjegyzék
Mi az érvényes zárójelek problémája?
Kezdjük azzal a kérdéssel, hogy mi az érvényes zárójel probléma?
Adott egy karakterlánc, amely egyszerű zárójeleket, göndör és szögletes kapcsos zárójeleket tartalmaz: () [] {}, akkor ellenőrizni kell, hogy a megadott zárójel-kombináció érvényes-e vagy sem.
Egy érvényes zárójeles karakterlánc megfelel a következő két feltételnek:
Íme néhány példa az érvényes és érvénytelen zárójeles karakterláncokra.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
Problémamegoldó megközelítésünkben a verem az az adatstruktúra, amely kulcsszerepet fog játszani. Tekintsük át a verem alapjait a következő részben.
A verem adatszerkezet újralátva
A verem egy LIFO (last in first out) adatstruktúra, ahol elemeket adhatunk a verem tetejéhez, és eltávolíthatjuk őket a verem tetejéről.
Amikor hozzáad egy elemet a verem tetejéhez, akkor push műveletet hajt végre, amikor eltávolít egy elemet a verem tetejéről, pop műveletet hajt végre.
A következő két szabályt használjuk, hogy kidolgozzunk egy sor műveletet, amelyet a zárójelben lévő karakterláncon hajthatunk végre.
- Tolja az összes nyitó tartót a kötegre.
- Ha zárókonzolra bukkan, pattintsa le a verem tetejét.
Folytassuk az érvényes zárójel-ellenőrzési probléma megoldásával.
Az érvényes zárójelek ellenőrzése
Összefoglalva a fenti példák összes megfigyelését, a következőket kapjuk.
Ellenőrizze a zárójelben lévő karakterlánc hosszát: Ha páratlan, a karakterlánc érvénytelen
Mivel minden nyitó zárójelnek kell lennie egy záró zárójelnek, az érvényes karakterláncnak páros számú karaktert kell tartalmaznia. Ha a karakterlánc hossza páratlan, azonnal arra a következtetésre juthat, hogy érvénytelen a zárójelek kombinációja.
# 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 = "{())}"
Ezután nézzük meg, hogyan kezelhetjük, ha a karakterláncban páros a karakterek száma
A zárójelben lévő karakterlánc hossza páros: mi lesz ezután?
1. lépés: Haladjon át a karakterláncon balról jobbra. Nevezzük a test_str karakterláncot és a karakterlánc egyes karaktereit char-nak.
2. lépés: Ha az első karakter egy nyitó zárójel (, {, vagy [, 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 = “()]”
- Az első karakter ( egy nyitó zárójel; tolja a verembe.
- A második karakter ) egy záró zárójel; pattintsa le a verem tetejét, ami történetesen ) – egy azonos típusú nyitó tartó. Folytassa a következő karakterrel.
- A harmadik karakter ]egy záró szögletes zárójel, és ismét le kell ugrani a verem tetejéről. Azonban amint láthatja, a verem üres – ami azt jelenti, hogy nincs megfelelő nyitó zárójel [. 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 ‘}’, ‘]’, ‘)’ értékként. A .keys() metódussal elérheti a szótár egyes kulcsait.
Használjuk mindazt, amit megtanultunk az is_valid() függvény definíciójának megírásához.
A függvénydefiníció megértése
Olvassa el a függvénydefiníciót tartalmazó következő kódcellát. Láthatja, hogy a folyamatábra lépéseit a fenti magyarázattal párhuzamosan alkalmaztuk.
Ezenkívül hozzáadtuk a docstring beleértve:
- a funkció rövid leírása
- a függvényhívás argumentumait
- a függvény visszatérési értékeit
▶ A docstring lekéréséhez használhatja a help(is_valid) vagy az is_valid.__doc__ parancsot.
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 == []
A Python is_valid függvény ellenőrzi, hogy a zárójelben szereplő karakterlánc érvényes-e, és a következőképpen működik.
- Az is_valid függvény egy paramétert vesz fel, a test_str, amely az érvényesítendő zárójelben szereplő karakterlánc. Igaz vagy hamis értéket ad vissza attól függően, hogy a test_str karakterlánc érvényes-e vagy sem.
- Itt a verem a Python lista, amely emulálja a veremet.
- A par_dict pedig a Python szótár, amelyben a nyitó zárójelek a kulcsok, a záró zárójelek pedig a megfelelő értékek.
- A karakterlánc bejárása során, ha olyan feltételbe ütközünk, amely érvénytelenné teszi a zárójeles karakterláncot, a függvény False értéket ad vissza, és kilép.
- Miután bejárta a karakterlánc összes karakterét, verem == [] ellenőrzi, hogy a verem üres-e. Ha igen, a teszt_str érvényes, és a függvény True értéket ad vissza. Ellenkező esetben a függvény False értéket ad vissza.
Most menjünk tovább, és hajtsunk végre néhány függvényhívást, hogy ellenőrizzük, hogy a függvény megfelelően működik-e.
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
A fenti kódrészletből arra következtethetünk, hogy a függvény a várt módon működik!
Következtetés 🧑💻
Íme egy gyors összefoglaló a tanultakról.
- Először is megismerkedtél az érvényes zárójelek ellenőrzésének problémájával.
- Ezután megtanult egy megközelítést a probléma megoldására, a verem segítségével választott adatszerkezetként.
- Ezután megtanulta, hogyan kell érvényesíteni a zárójel-kombinációt Python szótár használatával: nyitó zárójelek, billentyűk és a megfelelő záró zárójelek értékként.
- Végül meghatározta a Python függvényt, hogy ellenőrizze, hogy egy adott zárójeles karakterlánc érvényes-e.
Következő lépésként próbálja meg kódolni a problémát a etoppc.com online Python szerkesztőjében. Nyugodtan tekintse meg ezt az útmutatót, ha segítségre van szüksége!
Nézzen meg további Python oktatóanyagokat. Jó kódolást!🎉