Stosy do dopasowywania nawiasów
Weryfikowanie nawiasów za pomocą stosu
Stosy do dopasowywania nawiasów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Ostatni wchodzi, pierwszy wychodzi
Stos to struktura, w której ostatni dodany element jest pierwszym usuwanym, podobnie jak w stosie talerzy. 🍽️
Listy w Pythonie są stosami
W Pythonie nie trzeba używać specjalnej klasy. Zwykła lista już działa jako szybki, gotowy stos przydatny w konkursach programistycznych.
stack = []Dodawanie za pomocą append
Aby dodać element na wierzch stosu, wywołaj append, które umieszcza wartość na końcu listy w czasie O(1).
stack.append('(')
stack.append('[')Zdejmowanie ze szczytu
Wywołanie pop bez indeksu usuwa i zwraca ostatni element, czyli ten, który został ostatnio dodany na stos.
top = stack.pop() # removes '['Podgląd bez usuwania
Aby zobaczyć element na szczycie bez zdejmowania go ze stosu, wystarczy odczytać stack[-1]. Taki podgląd jest przydatny przed podjęciem decyzji o wykonaniu pop.
if stack:
top = stack[-1]Zawsze sprawdzaj, czy stos jest pusty
Wykonanie pop na pustym stosie powoduje błąd. Przed każdym pop należy sprawdzić if stack, aby rozwiązanie nigdy nie uległo awarii.
Idea dopasowywania nawiasów
Nawiasy zagnieżdżają się idealnie, więc aż proszą się o użycie stosu. Odkładaj każdy nawias otwierający, a zamykający musi pasować do elementu na szczycie stosu.
Mapowanie zamykających na otwierające
Utwórz mały słownik, który przypisuje każdemu nawiasowi zamykającemu oczekiwany nawias otwierający, aby sprawdzanie pozostało przejrzyste.
pairs = {')': '(', ']': '[', '}': '{'}Skanowanie i podejmowanie decyzji
Przejdź po napisie jeden raz. Odkładaj nawiasy otwierające, a przy zamykającym porównuj go ze zdjętym elementem ze szczytu za pomocą mapy pairs.
for c in s:
if c in pairs.values():
stack.append(c)Niezgodność oznacza niepoprawność
Jeśli zdjęty nawias otwierający nie pasuje albo stos jest pusty, gdy jest potrzebny, napis od razu jest niepoprawny.
elif not stack or stack.pop() != pairs[c]:
return FalsePusty stos na końcu
Jeśli po skanowaniu pozostał nawias otwierający, oznacza to, że czegoś nie zamknięto. Napis jest poprawny tylko wtedy, gdy stos ostatecznie jest pusty.
return not stackSzybkie sprawdzenie
Sprawdzają Państwo poprawność nawiasów za pomocą stosu. Co oznacza niepusty stos na samym końcu?
Podsumowanie: stosy ujarzmiają nawiasy
Nauczyli się Państwo, że lista działa jak stos: należy odkładać nawiasy otwierające, zdejmować je przy zamykających, a pusty stos na końcu oznacza poprawne zbilansowanie. Świetna praca! 🎉
Często zadawane pytania
Czy lekcja „Stosy do dopasowywania nawiasów” jest bezpłatna?
Tak — pełny tekst „Stosy do dopasowywania nawiasów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Stosy do dopasowywania nawiasów”?
Weryfikowanie nawiasów za pomocą stosu Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Stosy do dopasowywania nawiasów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Stosy do dopasowywania nawiasów
- Stos monotoniczny: następny większy element
- Kolejki i collections.deque
- Maksimum w przesuwanym oknie za pomocą deque