W tym przewodniku zgłębisz tajniki weryfikacji poprawności konstrukcji nawiasowych w języku Python.
Analiza, czy sekwencja nawiasów jest prawidłowa, stanowi powszechne zadanie podczas rekrutacji programistów. W ciągu kilku nadchodzących minut poznasz skuteczną metodę rozwiązania tego problemu. Dodatkowo, stworzysz funkcję w Pythonie, która automatycznie oceni poprawność danego ciągu.
Na czym polega problem z poprawnym nawiasowaniem?
Zacznijmy od wyjaśnienia, na czym dokładnie polega problem poprawnego nawiasowania.
Twoim zadaniem jest, na podstawie wprowadzonego ciągu znaków składającego się z nawiasów okrągłych, klamrowych i kwadratowych: () [] {}, określić, czy ich kombinacja jest poprawna.
Prawidłowo zbudowany ciąg nawiasów musi spełniać następujące dwa kryteria:
- Każdy nawias otwierający musi posiadać odpowiadający mu nawias zamykający tego samego rodzaju.
- Nawiasy muszą być zamykane we właściwej kolejności.
Poniżej znajdziesz przykłady prawidłowych i nieprawidłowych sekwencji nawiasowych.
test_str = "{}]" --> NIEPRAWIDŁOWY, ] nie został nigdy otwarty
test_str = "[{}]" --> PRAWIDŁOWY
test_str = "[]" --> PRAWIDŁOWY
test_str = "[]{}" --> PRAWIDŁOWY
test_str = "[{]}" --> NIEPRAWIDŁOWY, nawiasy zamknięte w złej kolejności!
W naszym podejściu kluczową rolę odegra struktura danych zwana stosem. Przyjrzyjmy się zatem jego podstawowym zasadom.
Powtórka wiadomości o strukturze danych stosu
Stos to struktura danych działająca na zasadzie „ostatnie weszło, pierwsze wyszło” (LIFO). Elementy są dodawane na wierzch stosu i usuwane również z wierzchu.
Dodanie elementu na wierzch stosu to operacja „wepchnięcia”, a usunięcie elementu z wierzchu to operacja „ściągnięcia”.
Do analizy łańcucha nawiasów zastosujemy następujące dwie zasady:
- Wszystkie nawiasy otwierające wstawiamy na stos.
- Gdy napotkamy nawias zamykający, zdejmujemy element z wierzchołka stosu.
Przejdźmy teraz do omówienia rozwiązania problemu weryfikacji poprawności nawiasów.
Jak przeprowadzić walidację nawiasów?
Sumując obserwacje z wcześniejszych przykładów, otrzymujemy następujące wnioski.
Analiza długości ciągu nawiasów: Nieparzysta długość oznacza niepoprawność
Ponieważ każdy nawias otwierający wymaga swojego odpowiednika zamykającego, poprawny ciąg znaków powinien zawierać parzystą liczbę symboli. W przypadku nieparzystej długości ciągu, od razu możemy stwierdzić, że zawiera on nieprawidłową kombinację.
# len(test_str) = 3 (nieparzysta); ] nie ma otwierającego [
test_str = "{}]"
# len(test_str) = 3 (nieparzysta); ( nie ma zamykającego )
test_str = "[(]"
# len(test_str) = 5 (nieparzysta); występuje zbędny )
test_str = "{())}"
Zobaczmy, jak poradzić sobie w sytuacji, gdy liczba symboli w ciągu jest parzysta.
Parzysta długość ciągu nawiasów: co dalej?
Krok 1: Przeszukujemy łańcuch znaków od lewej do prawej. Nazwijmy łańcuch test_str, a poszczególne znaki char.
Krok 2: Jeśli napotkany znak jest nawiasem otwierającym (, { lub [, umieszczamy go na szczycie stosu i przechodzimy do kolejnego znaku.
Krok 3: Sprawdzamy, czy następny znak (char) jest nawiasem otwierającym czy zamykającym.
Krok 3.1: Jeżeli jest nawiasem otwierającym, dodajemy go na szczyt stosu.
Krok 3.2: Jeżeli natomiast napotkamy nawias zamykający, ściągamy element ze szczytu stosu i przechodzimy do kroku 4.
Krok 4: Tutaj mamy 3 różne możliwości, zależne od wartości ściągniętej ze stosu:
Krok 4.1: Jeżeli ściągnięty element jest nawiasem otwierającym tego samego typu, wracamy do kroku 3.
Krok 4.2: Jeżeli jest nawiasem otwierającym innego typu, możemy stwierdzić, że łańcuch nawiasów jest niepoprawny.
Krok 4.3: Ostatnia możliwość to sytuacja, gdy stos jest pusty. To także oznacza niepoprawny łańcuch, ponieważ natknęliśmy się na nawias zamykający, który nie ma pasującego nawiasu otwierającego.
Analiza przykładów poprawnych ciągów nawiasów
Przeanalizujmy trzy przykłady, aby przejść przez powyższe kroki.
📑 Jeśli rozumiesz już, jak to działa, możesz przejść do następnej sekcji.
#1. Na pierwszy przykład weźmy test_str = “{()”.
- { jest pierwszym znakiem i jest nawiasem otwierającym, więc umieszczamy go na stosie.
- Kolejny znak ( również jest nawiasem otwierającym, więc dodajemy go na stosie.
- Trzeci znak w łańcuchu ) jest nawiasem zamykającym, więc ściągamy element z wierzchu stosu, co zwraca (.
- W tym momencie dotarliśmy do końca ciągu znaków. Jednak stos nadal zawiera otwierający nawias { , który nie został zamknięty. Stąd ciąg nawiasów test_str jest niepoprawny.
#2. W drugim przykładzie rozważmy test_str = “()]”
- Pierwszy znak ( jest nawiasem otwierającym, więc dodajemy go na stos.
- Drugi znak ) to nawias zamykający, więc ściągamy wierzchołek stosu, którym jest ( – nawias otwierający tego samego typu. Przechodzimy do kolejnego znaku.
- Trzeci znak ] jest zamykającym nawiasem kwadratowym, więc powinniśmy ściągnąć wierzchołek stosu. Jednak, jak widzimy, stos jest pusty – co oznacza, że nie istnieje pasujący nawias otwierający [. Zatem ten łańcuch jest nieprawidłowy.
#3. W ostatnim przykładzie test_str = “{()}”.
- Pierwsze dwa znaki {( są nawiasami otwierającymi, więc umieszczamy je na stosie.
- Trzeci znak to ), więc ściągamy element z wierzchu stosu – (.
- Następny znak } jest zamykającym nawiasem klamrowym, a po ściągnięciu wierzchu stosu otrzymujemy { – otwierający nawias klamrowy.
- Po przejściu całego ciągu, stos jest pusty, a test_str jest prawidłowy! ✅
📌 Przygotowałem schemat blokowy, który przedstawia kolejne kroki weryfikacji poprawności nawiasów. Możesz go zachować jako szybkie odniesienie!
W kolejnej sekcji zobaczymy, jak przełożyć nasze koncepcje na kod w Pythonie.
Program w Pythonie do sprawdzania poprawności nawiasów
W Pythonie możemy użyć listy do symulowania stosu.
Możemy wykorzystać metodę .append(), aby dodawać elementy na koniec listy. To działanie odpowiada umieszczaniu na szczycie stosu.
Metoda .pop() zwraca ostatni element z listy, co odpowiada ściąganiu elementu z wierzchu stosu – czyli usunięciu ostatnio dodanego elementu.
Znasz już sposoby implementacji operacji wstawiania i usuwania elementu z listy w Pythonie, naśladując zachowanie stosu.
Następnie odpowiedzmy na pytanie: jak rozróżnić nawiasy otwierające od zamykających?
W tym celu możemy wykorzystać słownik Pythona – z nawiasami otwierającymi ‘{‘, ‘[‘, ‘(‘ jako kluczami i odpowiadającymi im nawiasami zamykającymi ‘}’, ‘]’, ‘)’ jako wartościami. Metoda .keys() umożliwi nam dostęp do poszczególnych kluczy słownika.
Wykorzystajmy zdobytą wiedzę do napisania definicji funkcji is_valid().
Analiza definicji funkcji
Przeanalizujmy poniższy kod, który zawiera definicję funkcji. Zastosowaliśmy w niej kroki ze schematu blokowego w połączeniu z wcześniejszymi wyjaśnieniami.
Dodatkowo, umieściliśmy dokumentację, zawierającą:
- krótki opis funkcji
- argumenty funkcji
- wartości zwracane przez funkcję
▶ Możesz użyć help(is_valid) lub is_valid.__doc__, aby uzyskać dostęp do dokumentacji.
def isValid(test_str):
'''Sprawdza, czy dany ciąg nawiasów jest poprawny.
Args:
test_str (str): Łańcuch nawiasów do weryfikacji
Returns:
True, jeśli test_str jest poprawny; False w przeciwnym wypadku
'''
# len(test_str) jest nieparzysta -> nieprawidłowy!
if len(test_str)%2 != 0:
return False
# inicjalizacja słownika nawiasów
par_dict = {'(':')','{':'}','[':']'}
stack = []
for char in test_str:
# dodaj nawias otwierający do stosu
if char in par_dict.keys():
stack.append(char)
else:
# nawias zamykający bez pasującego otwierającego
if stack == []:
return False
# jeśli nawias zamykający -> usuń ze szczytu stosu
open_brac = stack.pop()
# niepasujący nawias -> nieprawidłowy!
if char != par_dict[open_brac]:
return False
return stack == []
Funkcja is_valid w Pythonie weryfikuje poprawność ciągu nawiasów w następujący sposób:
- Funkcja is_valid przyjmuje jeden argument, test_str, który reprezentuje ciąg nawiasów do analizy. Funkcja zwraca True, jeśli ciąg test_str jest poprawny, w przeciwnym razie zwraca False.
- W tym przypadku stos jest reprezentowany przez listę w Pythonie, symulując strukturę stosu.
- Natomiast par_dict to słownik Pythona, w którym kluczami są nawiasy otwierające, a ich wartościami – nawiasy zamykające.
- Podczas analizy ciągu, jeśli natrafimy na warunek wskazujący na niepoprawność ciągu nawiasów, funkcja zwraca False i kończy działanie.
- Po przeanalizowaniu wszystkich znaków ciągu, sprawdzamy czy stos jest pusty. Jeżeli tak, to znaczy, że test_str jest prawidłowy i funkcja zwraca True. W przeciwnym razie funkcja zwraca False.
Wykonajmy kilka wywołań funkcji, aby sprawdzić, czy działa ona poprawnie.
str1 = '{}[]'
isValid(str1)
# Wynik: True
str2 = '{((}'
isValid(str2)
# Wynik: False
str3 = '[{()}]'
isValid(str3)
# Wynik: True
str4 = '[{)}]'
isValid(str4)
# Wynik: False
str5 = '[[]}'
isValid(str5)
# Wynik: False
Z powyższego kodu wynika, że funkcja działa zgodnie z oczekiwaniami!
Podsumowanie 🧑💻
Oto krótkie podsumowanie tego, czego się nauczyłeś:
- Na początku poznałeś problem weryfikacji poprawności nawiasów.
- Następnie, zapoznałeś się z podejściem do rozwiązania problemu przy użyciu struktury danych stosu.
- Dowiedziałeś się, jak weryfikować sekwencje nawiasów przy pomocy słownika Pythona, gdzie nawiasy otwierające pełnią rolę kluczy, a odpowiadające im nawiasy zamykające – wartości.
- Na koniec, zdefiniowałeś funkcję w Pythonie, która sprawdza, czy podany ciąg nawiasów jest poprawny.
W ramach ćwiczenia spróbuj zakodować rozwiązanie w edytorze online w newsblog.pl. Jeżeli będziesz potrzebować pomocy, wróć do tego poradnika!
Zapoznaj się z innymi tutorialami na temat Pythona. Udanej nauki programowania!🎉
newsblog.pl