Stos — i odwrotna notacja polska

🎯 Po co Ci to?

Naciśnij „cofnij" w edytorze — wróci ostatnia zmiana. Naciśnij jeszcze raz — przedostatnia. Zamknij karty przeglądarki „wstecz" — ostatnia odwiedzona pierwsza. Wywołaj funkcję, która wywołuje funkcję (7.1) — wróci najpierw ta najgłębsza. Wszystkie te zjawiska napędza jedna struktura o jednej żelaznej zasadzie: ostatni, który wszedł, wychodzi pierwszy. Stos jest tak fundamentalny, że siedzi w sercu każdego procesora (jako stos wywołań) i w każdym kalkulatorze (jako mechanizm liczenia wyrażeń). Poznasz go — i policzysz nim wyrażenie w notacji, którą wymyślił Polak.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• opisać stos przez jego dwie operacje (odłóż / zdejmij) i zasadę LIFO;
• wskazać zjawiska napędzane stosem (cofanie, wywołania funkcji, dopasowanie nawiasów);
• obliczyć wartość wyrażenia w odwrotnej notacji polskiej za pomocą stosu.

🔁 Przypomnij sobie

Z 7.1: stos wywołań — górna ramka wraca pierwsza (to był stos w naturze!); z 3.4: L.append (dołóż na koniec) i L.pop (zdejmij z końca) — to gotowe operacje stosu.

📘 Wyjaśnienie

📐 DEFINICJA — stos (LIFO): struktura z dwiema operacjami: odłóż (push — dodaj element na wierzch) i zdejmij (pop — usuń i zwróć element z wierzchu). Zasada LIFO (Last In, First Out): ostatni odłożony wychodzi pierwszy.

Po ludzku: sterta talerzy — dokładasz na górę, bierzesz z góry; do dolnego nie sięgniesz, nie zdjąwszy wierzchnich. Czym NIE jest: strukturą z dostępem do środka. Stos celowo udostępnia tylko wierzch — i ta dyscyplina jest jego siłą, nie ograniczeniem.

W Pythonie stos to zwykła lista używana zdyscyplinowanie: append odkłada, pop zdejmuje (oba z końca — $O(1)$, tani koniec tablicy z 9.1!). Cała sztuka polega na tym, że dotykasz tylko wierzchu.

Do czego LIFO? Wszędzie, gdzie trzeba „wrócić do ostatniego niezałatwionego":

• Cofanie (undo, wstecz): każda akcja odłożona na stos; „cofnij" zdejmuje ostatnią.
• Wywołania funkcji (7.1): każde wywołanie odłożone; wraca najgłębsze. To dosłownie stos.
• Dopasowanie nawiasów: przechodząc wyrażenie, odkładaj otwierające nawiasy; przy zamykającym zdejmij ze stosu i sprawdź, czy pasuje. Pusto na końcu = nawiasy się zgadzają.

Popis: odwrotna notacja polska (ONP). Zwykły zapis $3 + 4 \times 2$ wymaga reguł pierwszeństwa i nawiasów, żeby wiedzieć, że mnożenie idzie pierwsze. Polski logik Jan Łukasiewicz zauważył w latach 20. XX wieku, że jeśli operator postawić za argumentami, nawiasy i pierwszeństwo znikają całkowicie. W odwrotnej notacji polskiej (ONP) $3 + 4 \times 2$ zapisujemy 3 4 2 * + — i czyta się to jednoznacznie, bez ani jednego nawiasu. Kalkulatory i kompilatory liczą wyrażenia właśnie tak — a robią to stosem:

def onp(wyrazenie):                  # np. "3 4 2 * +"
    stos = []
    for token in wyrazenie.split():
        if token in "+-*/":
            b = stos.pop()           # zdejmij DWA argumenty (uwaga na kolejność!)
            a = stos.pop()
            if token == "+": stos.append(a + b)
            elif token == "-": stos.append(a - b)
            elif token == "*": stos.append(a * b)
            else: stos.append(a / b)
        else:
            stos.append(int(token))  # liczba: odłóż na stos
    return stos.pop()                # jedyny element = wynik

Reguła jest cudownie prosta: liczbę odłóż; operator — zdejmij dwa, policz, odłóż wynik. Prześledź 3 4 2 * +: odłóż 3 → [3]; odłóż 4 → [3,4]; odłóż 2 → [3,4,2]; * → zdejmij 2 i 4, odłóż 8 → [3,8]; + → zdejmij 8 i 3, odłóż 11 → [11]; wynik 11. Mnożenie zostało wykonane przed dodawaniem bez żadnej reguły pierwszeństwa — kolejność w zapisie ONP sama to wymusiła.

💭 Pomyśl: W kodzie b = stos.pop() idzie przed a = stos.pop(). Czemu kolejność ma znaczenie? Kiedy pomylenie jej da zły wynik, a kiedy przejdzie niezauważone?

Sprawdź odpowiedź

Stos zdejmuje w kolejności odwrotnej do wkładania: ostatnio odłożony argument to prawy operand ($b$), wcześniejszy — lewy ($a$). Dla + i * (przemiennych) pomyłka przejdzie niezauważona ($a+b = b+a$). Ale dla - i / da zły wynik: 5 3 - to $5 - 3 = 2$, a pomylone $3 - 5 = -2$. To klasyczna pułapka ONP i częsty błąd na sprawdzianach — LIFO odwraca kolejność, więc przy operatorach nieprzemiennych trzeba świadomie odtworzyć „lewy przed prawym". Zawsze testuj implementację ONP na odejmowaniu, nie na dodawaniu.

⚠️ Uwaga, pułapka

Stos ma dno — pop na pustym stosie to błąd. W ONP puste zdjęcie oznacza, że wyrażenie jest niepoprawne (za mało argumentów dla operatora, np. 3 +); a jeśli po przejściu całości na stosie zostaje więcej niż jeden element — też błąd (za mało operatorów, np. 3 4 5 +). Poprawne wyrażenie ONP zostawia dokładnie jeden element. Sprawdzanie tych warunków to nie pedanteria: tak właśnie kalkulator odróżnia poprawne wejście od bełkotu.

🌍 Powiązania

Stos jest wszędzie: mechanizm „wstecz" w przeglądarce i „cofnij" w edytorze, stos wywołań procesora (7.1), przechodzenie labiryntu w głąb (wchodzisz korytarzem, przy ślepym zaułku cofasz się do ostatniego rozgałęzienia — LIFO!), parsowanie języków (dopasowanie nawiasów w kodzie, znaczników w HTML). Nawet ewolucja rozwiązywania rekurencji „ręcznie" (7.2, zadanie 3) sprowadzała się do zbudowania własnego stosu. Gdy widzisz „ostatni załatwiany pierwszy" — myśl: stos.

🛠️ Teraz Ty

Bez komputera: policz ze stosem (rysując jego stany) wyrażenia ONP: 5 1 2 + 4 * + 3 - oraz 6 2 /. Zamień na ONP zwykłe (2 + 3) * 4. Z komputerem: zaimplementuj onp, przetestuj na powyższych i dopisz sprawdzanie poprawności (za mało/za dużo argumentów). Bonus: napisz czy_nawiasy_ok(tekst) sprawdzającą dopasowanie ()[]{} stosem.

📐 Definicje tej lekcji

• Stos (LIFO) — odłóż (push) / zdejmij (pop) z wierzchu; ostatni wchodzi, pierwszy wychodzi.
• Odwrotna notacja polska (ONP) — operator za argumentami; bez nawiasów i pierwszeństwa; liczona stosem (liczbę odłóż, operator: zdejmij dwa, policz, odłóż).

📌 Najważniejsze w pigułce

• Stos udostępnia tylko wierzch — i ta dyscyplina napędza cofanie, wywołania funkcji, dopasowanie nawiasów.
• ONP (Łukasiewicz) usuwa nawiasy i pierwszeństwo; kalkulatory liczą nią wyrażenia na stosie.
• LIFO odwraca kolejność — przy - i / pilnuj, który operand jest lewy; poprawne ONP zostawia jeden element.

🎒 Zadania

1. Policz stosem 4 5 + 6 2 - * — rysuj stan stosu po każdym tokenie i podaj wynik.

Wskazówka i odpowiedź

[4] → [4,5] → +: [9] → [9,6] → [9,6,2] → -: zdejmij 2 i 6, $6-2=4$, [9,4] → *: $9 \times 4 = 36$. Wynik 36 (odpowiada $(4+5) \times (6-2)$). Zauważ, jak - poprawnie dało $6-2$, nie $2-6$ — dlatego lewy operand to ten zdjęty jako drugi.

2. Zamień na ONP: (a) 3 * 4 + 5, (b) 3 * (4 + 5), (c) 2 + 3 * 4 - 1. Wskaż, gdzie nawiasy w zwykłym zapisie „zniknęły" do kolejności w ONP.

Wskazówka i odpowiedź

(a) 3 4 * 5 + (mnożenie pierwsze — bo operator * stoi wcześniej). (b) 3 4 5 + * (nawias wymusił dodawanie przed mnożeniem — w ONP + jest przed *). (c) 2 3 4 * + 1 -. Porównaj (a) i (b): różnica nawiasów w zwykłym zapisie stała się różnicą kolejności operatorów w ONP. To właśnie odkrycie Łukasiewicza: informację o pierwszeństwie da się zakodować w kolejności, bez nawiasów.

3. Napisz (lub opisz) sprawdzanie dopasowania nawiasów ([{}]) stosem. Co robisz przy otwierającym, co przy zamykającym, jak wykrywasz błąd?

Wskazówka i odpowiedź

Otwierający nawias → odłóż na stos. Zamykający → zdejmij ze stosu i sprawdź, czy pasuje typem () do (); jeśli stos pusty albo typ się nie zgadza → błąd (([)] się wysypie: przy ) na wierzchu jest [). Na końcu stos musi być pusty (każde otwarcie domknięte). To dokładnie tak działają edytory kodu, podświetlając niesparowany nawias — i tak parser sprawdza zagnieżdżenie znaczników HTML. Stos jest naturalnym narzędziem wszędzie, gdzie „najbardziej wewnętrzne domyka się pierwsze".

🔍 Sprawdź, czy umiesz

• Opisać stos dwiema operacjami i zasadą LIFO oraz podać trzy zjawiska nim napędzane.
• Policzyć wyrażenie ONP stosem, poprawnie obsługując odejmowanie.
• Sprawdzić dopasowanie nawiasów stosem i wskazać, kiedy zgłosić błąd.

---