V tomto tutoriálu se naučíte kontrolovat platné závorky v Pythonu.
Vzhledem k řetězci závorek je kontrola, zda je kombinace závorek platná, oblíbenou otázkou kódovacího rozhovoru. A během několika příštích minut se naučíte techniku řešení této otázky a také nakódujete funkci Pythonu pro ověření daného řetězce.
Table of Contents
Co je problém s platnými závorkami?
Začněme naši diskuzi odpovědí na otázku, jaký je problém platných závorek?
Zadaný řetězec obsahující znaky jednoduché závorky, složené a hranaté závorky: () [] {}, musíte zkontrolovat, zda je daná kombinace závorek platná.
Platný řetězec závorek splňuje následující dvě podmínky:
Zde je několik příkladů platných a neplatných řetězců závorek.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
V našem přístupu k řešení problémů je zásobník datovou strukturou, která bude hrát klíčovou roli. Podívejme se na základy zásobníku v další části.
Znovu navštívená datová struktura zásobníku
Zásobník je datová struktura LIFO (poslední dovnitř první ven), kde můžete přidávat prvky do horní části zásobníku a také je z horní části zásobníku odebírat.
Když přidáte prvek na vrchol zásobníku, provedete operaci push, když odstraníte prvek z vrcholu zásobníku, provedete operaci pop.
Následující dvě pravidla použijeme k vytvoření sady operací, které můžeme provádět s řetězcem závorek.
- Zatlačte všechny otevírací držáky na stoh.
- Pokud narazíte na uzavírací závorku, sejměte vršek stohu.
Pokračujme v řešení problému kontroly platných závorek.
Jak zkontrolovat platné závorky
Když dáme dohromady všechna pozorování z výše uvedených příkladů, máme následující.
Zkontrolujte délku řetězce závorek: Pokud je lichý, řetězec je neplatný
Protože každá hranatá závorka musí mít uzavírací závorku, platný řetězec by měl obsahovat sudý počet znaků. Pokud je délka řetězce lichá, můžete okamžitě usoudit, že obsahuje neplatnou kombinaci závorek.
# 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 = "{())}"
Dále se podívejme, jak se můžeme vypořádat s tím, když je počet znaků v řetězci sudý
Délka řetězce závorek je sudá: co dál?
Krok 1: Projeďte provázkem zleva doprava. Řekněme řetězec test_str a jednotlivé znaky v řetězci char.
Krok 2: Pokud je první znak znakem otevírací závorka (, {, nebo [, 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 = “()]“
- První znak ( je otevírací hranatá závorka; vložte jej do zásobníku.
- Druhý znak ) je závorka; odskočte vršek zásobníku, což je náhodou ) – otevírací závorka stejného typu. Pokračujte na další znak.
- Třetí znak ]je uzavírací hranatá závorka a měli byste znovu vyskočit z vrcholu zásobníku. Jak však vidíte, zásobník je prázdný – což znamená, že neexistuje žádná odpovídající otevírací závorka [. 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 ‘}’, ‘]‘, ‚)‘ jako hodnoty. Pro přístup k jednotlivým klíčům ve slovníku můžete použít metodu .keys().
Vše, co jsme se naučili, využijeme k napsání definice funkce is_valid().
Pochopení definice funkce
Přečtěte si následující buňku kódu obsahující definici funkce. Můžete vidět, že jsme použili kroky ve vývojovém diagramu v tandemu s výše uvedeným vysvětlením.
Kromě toho jsme také přidali a dokumentační řetězec počítaje v to:
- krátký popis funkce
- argumenty ve volání funkce
- návratové hodnoty z funkce
▶ K načtení řetězce dokumentů můžete použít help(is_valid) nebo is_valid.__doc__.
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 == []
Funkce is_valid v Pythonu kontroluje, zda je řetězec závorek platný, a funguje následovně.
- Funkce is_valid přebírá jeden parametr, test_str, což je řetězec závorek, který má být ověřen. Vrací hodnotu True nebo False v závislosti na tom, zda je řetězec test_str platný či nikoli.
- Zde je zásobník seznam Pythonu, který emuluje zásobník.
- A par_dict je pythonovský slovník, s otevíracími závorkami jako klíče a uzavíracími závorkami jako odpovídajícími hodnotami.
- Pokud při procházení řetězcem narazíme na jakoukoli podmínku, která způsobí neplatnost řetězce v závorkách, funkce vrátí hodnotu False a skončí.
- Po procházení všech znaků v řetězci stack == [] zkontroluje, zda je zásobník prázdný. Pokud ano, test_str je platný a funkce vrátí hodnotu True. Jinak funkce vrací False.
Nyní pojďme do toho a proveďte několik volání funkcí, abychom ověřili, že naše funkce funguje správně.
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
Z výše uvedeného úryvku kódu můžeme usoudit, že funkce funguje podle očekávání!
Závěr 🧑💻
Zde je rychlý souhrn toho, co jste se naučili.
- Nejprve jste byli seznámeni s problémem kontroly platných závorek.
- Dále jste se naučili přístup k řešení problému pomocí zásobníku jako zvolené datové struktury.
- Potom jste se naučili, jak ověřit kombinaci závorek pomocí slovníku Pythonu: s počátečními závorkami, klíči a odpovídajícími uzavíracími závorkami jako hodnotami.
- Nakonec jste definovali funkci Python pro kontrolu, zda je daný řetězec závorek platný.
Jako další krok zkuste problém zakódovat v online editoru Python etechblog.cz. Pokud potřebujete pomoc, neváhejte se vrátit k této příručce!
Podívejte se na další výukové programy Pythonu. Veselé kódování!🎉