Jak zkontrolovat platné závorky v Pythonu

V tomto návodu se seznámíte s postupem, jak v jazyce Python ověřit, zda je řetězec závorek platný.

Kontrola, zda je daná kombinace závorek (kulatých, hranatých a složených) správná, je častým úkolem při programovacích pohovorech. V následujících minutách si osvojíte techniku řešení tohoto problému a vytvoříte funkci v Pythonu, která dokáže takový řetězec zkontrolovat.

Problém s platnými závorkami: Co to vlastně je?

Začněme tím, že si vysvětlíme, o co vlastně v tomto problému jde.

Máme daný řetězec, který obsahuje různé typy závorek: (), [] a {}. Vaším úkolem je zjistit, zda je tato kombinace závorek platná.

Platný řetězec závorek musí splňovat dvě základní podmínky:

• Každá otevírací závorka musí mít odpovídající uzavírací závorku stejného typu.
• Závorky musí být uzavřeny ve správném pořadí.

Podívejme se na několik příkladů platných a neplatných řetězců závorek:

test_str = "{}]" --> NEPLATNÉ, závorka ] nebyla nikdy otevřena
test_str = "[{}]" --> PLATNÉ
test_str = "[]" --> PLATNÉ
test_str = "[]{}" --> PLATNÉ
test_str = "[{]}" --> NEPLATNÉ, závorky jsou uzavřeny v nesprávném pořadí!

Pro řešení tohoto problému budeme využívat datovou strukturu nazývanou zásobník. Podívejme se na základy zásobníku v následující části.

Zásobník jako datová struktura

Zásobník je datová struktura typu LIFO (Last In, First Out), což znamená, že poslední prvek, který byl do zásobníku přidán, je první prvek, který z něj bude odebrán. Prvky se přidávají na vrchol zásobníku a také se z něj odebírají.

Přidání prvku na vrchol zásobníku se nazývá operace push a odstranění prvku z vrcholu se nazývá pop.

Pro práci s řetězcem závorek použijeme následující pravidla:

• Každou otevírací závorku vložíme na zásobník (push).
• Když narazíme na uzavírací závorku, odebereme prvek z vrcholu zásobníku (pop).

Pojďme se nyní podívat, jak konkrétně kontrolovat, zda je řetězec závorek platný.

Postup pro kontrolu platných závorek

Z předchozích příkladů můžeme odvodit následující kroky:

Kontrola délky řetězce: Lichá délka znamená neplatnost

Protože každá otevírací závorka musí mít odpovídající uzavírací závorku, platný řetězec musí obsahovat sudý počet znaků. Pokud je délka řetězce lichá, můžeme okamžitě říci, že řetězec není platný.

# len(test_str) = 3 (lichá); ] nemá otevírací [
test_str = "{}]"

# len(test_str) = 3 (lichá); ( nemá uzavírací )
test_str = "[(]"

# len(test_str) = 5 (lichá); nadbytečná )
test_str = "{())}"

Dále se podíváme, jak postupovat, pokud je počet znaků v řetězci sudý.

Sudá délka řetězce: Co dál?

Krok 1: Projděte řetězec zleva doprava. Řekněme, že náš řetězec se jmenuje test_str a jednotlivé znaky jsou uloženy v proměnné char.

Krok 2: Pokud je aktuální znak (char) otevírací závorka (tj. (, { nebo [), vložte ji na vrchol zásobníku (push) a přejděte na další znak v řetězci.

Krok 3: Zkontrolujte, zda je další znak (char) otevírací nebo uzavírací závorka.

Krok 3.1: Pokud je otevírací, vložte ji opět na zásobník.

Krok 3.2: Pokud je uzavírací, odeberte prvek z vrcholu zásobníku (pop) a pokračujte krokem 4.

Krok 4: Zde mohou nastat 3 situace v závislosti na odebraném prvku:

Krok 4.1: Pokud je odebraný prvek otevírací závorka stejného typu jako aktuální uzavírací závorka, vraťte se ke kroku 3.

Krok 4.2: Pokud je odebraný prvek otevírací závorka jiného typu, můžeme usoudit, že řetězec není platný.

Krok 4.3: Poslední možnost je, že zásobník je prázdný. I v tomto případě je řetězec neplatný, protože jsme narazili na uzavírací závorku, která nemá odpovídající otevírací závorku.

Příklady: Kontrola platnosti řetězce závorek

Podívejme se na tři příklady a projděte si výše uvedené kroky.

📑 Pokud už tomu rozumíte, klidně přeskočte na další sekci.

#1. Jako první příklad uvažujme řetězec test_str = „{()“.

• První znak { je otevírací závorka, takže ji vložíme na zásobník.
• Druhý znak ( je také otevírací závorka, takže ji také vložíme na zásobník.
• Třetí znak v řetězci ) je uzavírací závorka, takže odebereme prvek z vrcholu zásobníku, což je (.
• V tomto bodě jsme se dostali na konec řetězce. Ale na zásobníku stále zůstala otevírací závorka {, která nebyla nikdy uzavřena. Proto je daný řetězec závorek test_str neplatný.

#2. Jako druhý příklad si vezmeme řetězec test_str = „()]“.

• První znak ( je otevírací závorka; vložte ji na zásobník.
• Druhý znak ) je uzavírací závorka; odebereme prvek z vrcholu zásobníku, což je náhodou ( – otevírací závorka stejného typu. Pokračujte dalším znakem.
• Třetí znak ] je uzavírací hranatá závorka a měli bychom znovu odebrat prvek z vrcholu zásobníku. Jak ale vidíme, zásobník je prázdný – což znamená, že neexistuje žádná odpovídající otevírací závorka [. Tedy tento řetězec je neplatný.

#3. V posledním příkladu máme test_str = „{()}“.

• První dva znaky {( jsou otevírací závorky, takže je vložíme na zásobník.
• Třetí znak ) je uzavírací závorka, takže odebereme prvek z vrcholu zásobníku – (.
• Další znak } je uzavírací složená závorka a když odebereme prvek z vrcholu zásobníku, dostaneme { – otevírací složenou závorku.
• Po projití celého řetězce je zásobník prázdný a test_str je platný! ✅

📌 Připravil jsem pro vás vývojový diagram shrnující kroky pro ověření platnosti závorek. Můžete si ho uložit pro rychlou orientaci!

V další sekci se podíváme, jak tento koncept převedeme do kódu v Pythonu.

Program v Pythonu pro kontrolu platných závorek

V Pythonu můžeme pro simulaci zásobníku použít seznam.

Metodou .append() můžeme přidávat prvky na konec seznamu. To se podobá vkládání na vrchol zásobníku.

Metoda .pop() vrací poslední prvek ze seznamu, což se podobá odebírání prvku z vrcholu zásobníku – tj. odstranění posledního přidaného prvku.

Nyní už víte, jak pomocí seznamu v Pythonu simulovat operace push a pop na zásobníku.

Dalším krokem je odpovědět na otázku: jak rozlišit otevírací a uzavírací závorky?

Můžeme použít slovník v Pythonu – s otevíracími závorkami ‚{‚, ‚[‚, ‚(‚ jako klíči a odpovídajícími uzavíracími závorkami ‚}‘, ‚]‘, ‚)‘ jako hodnotami. K jednotlivým klíčům ve slovníku můžeme přistupovat pomocí metody .keys().

Všechny dosavadní znalosti nyní využijeme k napsání definice funkce is_valid().

Definice funkce a její popis

Prohlédněte si následující kód, který obsahuje definici funkce. Všimněte si, že jsme použili kroky uvedené ve vývojovém diagramu v kombinaci s výše uvedeným vysvětlením.

Kromě toho jsme přidali i dokumentační řetězec, který obsahuje:

• krátký popis funkce
• argumenty funkce
• návratové hodnoty funkce

▶ K zobrazení dokumentačního řetězce můžeme použít help(is_valid) nebo is_valid.__doc__.

def isValid(test_str):
  '''Ověří, zda je zadaný řetězec závorek platný.

  Args:
    test_str (str): Řetězec závorek, který má být ověřen.
  
  Returns:
    True, pokud je test_str platný; jinak False.
  '''
  # len(test_str) je lichá -> neplatné!
  if len(test_str)%2 != 0:
    return False
  # inicializace slovníku závorek
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # vložení otevírací závorky na zásobník
    if char in par_dict.keys():
      stack.append(char)
    else:
      # uzavírací závorka bez odpovídající otevírací
      if stack == []:
          return False
      # pokud je uzavírací, odebereme prvek z vrcholu zásobníku
      open_brac = stack.pop()
      # neodpovídající závorka -> neplatné!
      if char != par_dict[open_brac]:
        return False
  return stack == []

Funkce is_valid v Pythonu ověřuje, zda je řetězec závorek platný, a funguje takto:

• Funkce is_valid přijímá jeden parametr, test_str, což je řetězec závorek, který se má ověřit. Vrací hodnotu True nebo False v závislosti na tom, zda je řetězec test_str platný nebo ne.
• Zásobník je zde reprezentován seznamem v Pythonu.
• par_dict je slovník v Pythonu, kde klíči jsou otevírací závorky a hodnotami jsou odpovídající uzavírací závorky.
• Při procházení řetězcem, pokud narazíme na jakoukoli situaci, která způsobí, že je řetězec závorek neplatný, funkce vrátí hodnotu False a ukončí se.
• Po projití všech znaků v řetězci se provede kontrola, zda je zásobník prázdný (stack == []). Pokud ano, test_str je platný a funkce vrátí True. Jinak funkce vrátí False.

Nyní si zkusíme zavolat funkci s různými vstupy a ověřit, zda funguje správně.

str1 = '{}[]'
isValid(str1)
# Výstup: True

str2 = '{((}'
isValid(str2)
# Výstup: False

str3 = '[{()}]'
isValid(str3)
# Výstup: True

str4 = '[{)}]'
isValid(str4)
# Výstup: False

str5 = '[[]}'
isValid(str5)
# Výstup: False

Z výše uvedeného výstupu vidíme, že naše funkce funguje tak, jak má!

Závěr 🧑‍💻

Zde je rychlé shrnutí toho, co jste se naučili:

• Nejprve jste se seznámili s problémem ověřování platnosti řetězce závorek.
• Dále jste se naučili, jak k řešení tohoto problému použít datovou strukturu zásobník.
• Pak jste zjistili, jak pomocí slovníku v Pythonu ověřit kombinaci závorek – kde klíči jsou otevírací závorky a hodnotami jsou jim odpovídající závorky uzavírací.
• Nakonec jste vytvořili funkci v Pythonu, která kontroluje, zda je daný řetězec závorek platný.

Jako další krok si zkuste tento problém vyzkoušet v online editoru Pythonu na webu etechblog.cz. Pokud budete potřebovat pomoc, neváhejte se k tomuto návodu vrátit!

Podívejte se i na další návody k Pythonu. Příjemné kódování! 🎉