Stos, kolejka i odwrotna notacja polska

Stos to struktura danych, w której dokłada się i zdejmuje elementy z wierzchu (ostatni wszedł, pierwszy wychodzi). Kolejka wydaje elementy w kolejności przyjścia (pierwszy wszedł, pierwszy wychodzi). Stos jest kluczem do dwóch klasycznych zadań: obliczania wyrażeń w odwrotnej notacji polskiej (ONP) i sprawdzania poprawności nawiasów.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Podgląd zmiennych pokazuje zawartość stosu po każdym kroku.

Przejdź obliczanie wyrażenia w ONP krok po kroku

Stos i kolejka w Pythonie

from collections import deque

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack)

queue = deque()
queue.append("Ala")
queue.append("Olek")
queue.append("Ewa")
print(queue.popleft(), list(queue))

3 [1, 2]
Ala ['Olek', 'Ewa']

Obliczanie wyrażenia w ONP

Wyrażenie (3 + 4) · 2 w ONP to 3 4 + 2 *. Liczby trafiają na stos, a działanie zdejmuje dwie ostatnie liczby i kładzie wynik:

def evaluate_rpn(expression):
    stack = []
    for token in expression.split():
        if token in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(a // b)
        else:
            stack.append(int(token))
    return stack[0]


print(evaluate_rpn("3 4 + 2 *"))
print(evaluate_rpn("5 1 2 + 4 * + 3 -"))

14
14

Kolejność zdejmowania jest ważna: najpierw zdejmuje się drugi argument (b), potem pierwszy (a). Przy dodawaniu to bez znaczenia, ale 9 2 - to 7, a nie -7.

Poprawność nawiasów

Każdy nawias otwierający kładzie na stos nawias, który musi go zamknąć. Nawias zamykający musi być taki sam jak wierzch stosu:

def brackets_ok(text):
    stack = []
    pairs = {"(": ")", "[": "]", "{": "}"}
    for c in text:
        if c in pairs:
            stack.append(pairs[c])
        elif c in ")]}":
            if not stack or stack.pop() != c:
                return False
    return not stack


for text in ["([()])", "([)]", "(()", "a(b)c[d]"]:
    print(text, brackets_ok(text))

([()]) True
([)] False
(() False
a(b)c[d] True

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Wartość wyrażenia w odwrotnej notacji polskiej

Specyfikacja. Dane: wyrażenie w ONP jako n elementów W[1..n]: liczby całkowite i działania +, -, *, / (dzielenie całkowite). Wynik: wartość wyrażenia.

Lista kroków:

1. Wczytaj n i elementy W[1..n]. Stos S jest pusty (t = 0 to liczba elementów na stosie).
2. Dla kolejnych elementów c = W[i] wykonaj kroki 3-4.
3. Jeśli c jest działaniem, zdejmij ze stosu dwie liczby: b (wierzch) i a (pod nią), oblicz a c b i połóż wynik na stos.
4. Jeśli c jest liczbą, połóż ją na stos.
5. Wypisz jedyny element stosu S[1].

Pseudokod:

wczytaj n, W
t ← 0
dla i = 1, 2, ..., n wykonuj
  c ← W[i]
  jeżeli c = "+" lub c = "-" lub c = "*" lub c = "/" to
    b ← S[t]
    a ← S[t - 1]
    t ← t - 1
    jeżeli c = "+" to
      S[t] ← a + b
    jeżeli c = "-" to
      S[t] ← a - b
    jeżeli c = "*" to
      S[t] ← a * b
    jeżeli c = "/" to
      S[t] ← a div b
  w przeciwnym razie
    t ← t + 1
    S[t] ← liczba(c)
wypisz S[1]

Schemat blokowy:

Poprawność nawiasów ze stosem

Specyfikacja. Dane: napis s z nawiasami okrągłymi i kwadratowymi (inne znaki są pomijane). Wynik: TAK, gdy każdy nawias ma parę tego samego rodzaju we właściwej kolejności, w przeciwnym razie NIE.

Lista kroków:

1. Wczytaj napis s. Stos S jest pusty (t = 0), ok = prawda.
2. Dla kolejnych znaków c napisu wykonaj kroki 3-4.
3. Jeśli c to ( albo [, połóż na stos nawias, który musi go zamknąć: ) albo ].
4. Jeśli c to ) albo ], a stos jest pusty albo na wierzchu leży inny nawias, ustaw ok = fałsz. W przeciwnym razie zdejmij wierzch stosu.
5. Wypisz TAK, gdy ok = prawda i stos jest pusty, w przeciwnym razie NIE.

Pseudokod:

wczytaj s
t ← 0
ok ← prawda
dla i = 1, 2, ..., długość(s) wykonuj
  c ← s[i]
  jeżeli c = "(" lub c = "[" to
    t ← t + 1
    jeżeli c = "(" to
      S[t] ← ")"
    w przeciwnym razie
      S[t] ← "]"
  w przeciwnym razie
    jeżeli c = ")" lub c = "]" to
      jeżeli t > 0 i S[t] = c to
        t ← t - 1
      w przeciwnym razie
        ok ← fałsz
jeżeli ok i t = 0 to
  wypisz "TAK"
w przeciwnym razie
  wypisz "NIE"

Schemat blokowy:

Najczęstsze błędy

• Odwrócone argumenty. W ONP pierwszy zdjęty ze stosu jest prawy argument. Odejmowanie i dzielenie dają wtedy zły wynik.
• Zdejmowanie z pustego stosu. Nawias zamykający bez pary albo za mało liczb przed działaniem kończy się błędem IndexError. Sprawdź, czy stos nie jest pusty.
• Pusty stos na końcu nie sprawdzony. Napis (() przechodzi pętlę bez błędu, ale zostawia na stosie niezamknięty nawias.
• Kolejka na liście z pop(0). Działa, ale wolno dla dużych danych. Użyj collections.deque.

Ćwicz w przeglądarce

W temacie o stosie i kolejce kursu Algorytmy: zakres rozszerzony:

• stos: sprawdzanie nawiasów,
• kolejka: kto pierwszy, ten lepszy,
• zamiana wyrażenia na ONP,
• kalkulator ONP na liczbach całkowitych.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Pełna lista: algorytmy.

Dla nauczycieli

Stos najlepiej zrozumieć, rysując go na tablicy i porównując z podglądem zmiennych podczas krokowania. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.