Jak sprawdzić poprawność nawiasów w Pythonie?

W tym samouczku nauczysz się sprawdzać poprawność nawiasów w Pythonie.

Po podaniu ciągu nawiasów sprawdzanie, czy kombinacja nawiasów jest prawidłowa, jest popularnym pytaniem dotyczącym kodowania podczas rozmowy kwalifikacyjnej. W ciągu następnych kilku minut nauczysz się techniki rozwiązywania tego pytania, a także zakodujesz funkcję Pythona, aby sprawdzić poprawność danego łańcucha.

Spis treści:

Co to jest problem z prawidłowymi nawiasami?

Zacznijmy naszą dyskusję od odpowiedzi na pytanie, jaki jest problem z prawidłowymi nawiasami?

Biorąc pod uwagę ciąg znaków zawierający proste nawiasy, nawiasy klamrowe i kwadratowe: () [] {}, musisz sprawdzić, czy podana kombinacja nawiasów jest prawidłowa.

Prawidłowy ciąg nawiasów spełnia dwa następujące warunki:

Każdy nawias otwierający musi mieć pasujący nawias zamykający tego samego typu.

Wsporniki powinny być zamknięte we właściwej kolejności.

Oto kilka przykładów prawidłowych i nieprawidłowych ciągów nawiasów.

test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

W naszym podejściu do rozwiązywania problemów stos jest strukturą danych, która będzie odgrywać kluczową rolę. Przyjrzyjmy się podstawom stosu w następnej sekcji.

Ponowna analiza struktury danych stosu

Stos jest strukturą danych „ostatnie weszło, pierwsze wyszło” (LIFO), w której można dodawać elementy na szczyt stosu, a także usuwać je ze szczytu stosu.

Kiedy dodajesz element do szczytu stosu, wykonujesz operację wypychania, gdy usuwasz element ze szczytu stosu, wykonujesz operację wypychania.

Użyjemy następujących dwóch reguł, aby wymyślić zestaw operacji, które możemy wykonać na łańcuchu nawiasów.

Wepchnij wszystkie wsporniki otwierające na stos.
Jeśli natkniesz się na nawias zamykający, zdejmij górę stosu.

Przejdźmy do rozwiązania problemu sprawdzania poprawnych nawiasów.

Jak sprawdzić poprawność nawiasów?

Zestawiając wszystkie obserwacje z powyższych przykładów, mamy co następuje.

Sprawdź długość ciągu nawiasów: Jeśli nieparzysty, ciąg jest nieprawidłowy

Ponieważ każdy nawias otwierający musi mieć nawias zamykający, poprawny ciąg powinien zawierać parzystą liczbę znaków. Jeśli długość ciągu jest nieparzysta, możesz od razu stwierdzić, że zawiera nieprawidłową kombinację nawiasów.

# 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 = "{())}"

Następnie zobaczmy, jak możemy poradzić sobie, gdy liczba znaków w ciągu jest parzysta

Długość ciągu nawiasów jest parzysta: co dalej?

Krok 1: Przesuń strunę od lewej do prawej. Nazwijmy ciąg test_str, a poszczególne znaki w ciągu znaków.

Krok 2: Jeśli pierwszy znak jest nawiasem otwierającym (, { lub [, 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 = “()]”

Pierwszy znak ( jest nawiasem otwierającym; wstaw go na stos.
Drugi znak ) to nawias zamykający; pop off wierzchu stosu, którym jest ) – nawias otwierający tego samego typu. Przejdź do następnego znaku.
Trzeci znak ]jest zamykającym nawiasem kwadratowym i powinieneś ponownie zdjąć wierzch stosu. Jednak, jak widać, stos jest pusty — co oznacza, że nie ma pasującego nawiasu otwierającego [. 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 wartości. Możesz użyć metody .keys(), aby uzyskać dostęp do poszczególnych kluczy w słowniku.

Wykorzystajmy wszystko, czego się nauczyliśmy, aby napisać definicję funkcji is_valid().

Zrozumienie definicji funkcji

Przeczytaj następującą komórkę kodu zawierającą definicję funkcji. Widać, że wykorzystaliśmy kroki na schemacie blokowym w połączeniu z powyższym wyjaśnieniem.

Ponadto dodaliśmy również dokumentacja włącznie z:

krótki opis funkcji
argumenty w wywołaniu funkcji
zwracane wartości z funkcji

▶ Możesz użyć help(is_valid) lub is_valid.__doc__, aby pobrać dokument.

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 == []

Funkcja is_valid Pythona sprawdza, czy ciąg nawiasów jest poprawny i działa w następujący sposób.

Funkcja is_valid przyjmuje jeden parametr, test_str, który jest ciągiem nawiasów, który ma zostać zweryfikowany. Zwraca True lub False w zależności od tego, czy ciąg test_str jest poprawny.
Tutaj stos jest listą Pythona, która emuluje stos.
A par_dict to słownik Pythona z nawiasami otwierającymi jako kluczami i nawiasami zamykającymi jako odpowiednimi wartościami.
Podczas przechodzenia przez łańcuch, jeśli napotkamy jakikolwiek warunek, który powoduje, że łańcuch nawiasów jest nieprawidłowy, funkcja zwraca False i kończy działanie.
Po przejściu wszystkich znaków w ciągu, stos == [] sprawdza, czy stos jest pusty. Jeśli tak, test_str jest prawidłowy, a funkcja zwraca True. W przeciwnym razie funkcja zwraca False.

Teraz przejdźmy dalej i wykonajmy kilka wywołań funkcji, aby sprawdzić, czy nasza funkcja działa poprawnie.

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 powyższego fragmentu kodu możemy wywnioskować, że funkcja działa zgodnie z oczekiwaniami!

Wniosek 🧑‍💻

Oto krótkie podsumowanie tego, czego się nauczyłeś.

Po pierwsze, zapoznałeś się z problemem sprawdzania poprawności nawiasów.
Następnie poznałeś podejście do rozwiązania problemu przy użyciu stosu jako wybranej struktury danych.
Następnie nauczyłeś się, jak sprawdzać kombinację nawiasów za pomocą słownika Pythona: z nawiasami otwierającymi, kluczami i odpowiadającymi im nawiasami zamykającymi jako wartościami.
Na koniec zdefiniowałeś funkcję Pythona, aby sprawdzić, czy podany ciąg w nawiasach jest poprawny.

W następnym kroku spróbuj zakodować problem w internetowym edytorze Python w newsblog.pl. Jeśli potrzebujesz pomocy, wróć do tego przewodnika!

Sprawdź więcej samouczków Pythona. Udanego kodowania!🎉