Stos

Małgorzata Piekarska

Wstęp

Program może przetwarzać listę jednokierunkową w pewien specyficzny sposób.
Jeżeli przetwarzając listę jednokierunkową dodajemy do niej kolejne składniki zawsze na początek, zaś po przetworzeniu usuwamy z listy jej pierwszy składnik, to taką strukturę nazywamy stosem. Stos można sobie łatwo wyobrazić jako stertę ułożonych jedna na drugiej monet - zawsze można dołożyć monetę na szczycie stosu, a usunąć można jedynie monetę znajdującą się na szczycie.
W organizacji stosu obowiązuje zasada ostatni przyszedł, pierwszy wychodzi (Last In First Out - LIFO)

Rozróżniamy następujące elementarne operacje na stosie:

  • Sprawdzenie, czy stos jest pusty (funkcja, która zwraca true jeśli stos jest pusty),
  • Odczyt elementu ze szczytu stosu (funkcja, która zwraca element (zwykle wskaźnik) znajdujący się na szczycie stosu, sam element pozostaje na stosie),
  • Zapis na stos (funkcja, która umieszcza na szczycie stosu nowy element),
  • Usunięcie ze stosu (funkcja, która usuwa element ze szczytu stosu).

Przykład zastosowania stosu - ONP

Stos znajduje zastosowanie między innymi przy obliczaniu wartości wyrażenia zapisanego w Odwrotnej Notacji Polskiej (ONP lub ang.RPN).
ONP jest takim sposobem zapisu wyrażeń arytmetycznych, że znak operacji umieszczony jest tuż po operandach (zapis postfiksowy) a nie pomiędzy nimi jak w standardowym zapisie algebraicznym (zapis infiksowy). W zapisie wyrażenia w ONP nie występują nawiasy, dzięki czemu obliczenia stają się bardzo łatwe do przeprowadzania na komputerze, a kolejność wykonywania działań zostaje wyznaczona przez położenie operandów.

Przykład:
w klasycznym zapisie (infiksowym) 4+2
w ONP (zapisie postfiksowym) 4 2 +
w zapisie prefiksowym + 4 2

Obliczanie wartości wyrażenia zapisanego w ONP

Algorytmu obliczania wartości wyrażenia zapisanego w ONP jest bardzo prosty. Polega na tym, że jeśli w wyrażeniu (czytanym od lewej strony) pojawia się liczba, to wkładamy ją na stos, natomiast jeśli pojawia się operator, to ze stosu zdejmowane są jego argumenty (tyle argumentów ile wymaga dany operator), a na stos trafia zamiast tego wynik działania. Ostateczny wynik jest odczytywany ze stosu.

Przykładowo dla wyrażenia:

5 4 3 + *

zmiany zawartości stosu wyglądają następująco:
5 // pojawiła się liczba - na stos
5 4 //kolejna liczba na stos
5 4 3 //i jeszcze jedna
5 7 //nadszedł plus, więc zdjęliśmy ze stosu dwa argumenty i dodaliśmy 3 + 4, wynik trafił na stos
35 //nadszedł operator mnożenia więc zdjęliśmy ze stosu dwa argumenty i wykonaliśmy mnożenie

W wyniku otrzymujemy na stosie 35

Konwersja z notacji konwencjonalnej do ONP

Do konwersji pomiędzy notacją konwencjonalną, a ONP służy następujący algorytm:
Pamiętając, że (podobnie jak w systemie konwencjonalnym) tak i tu obowiązują standardowe priorytety operatorów, należy wykonywać następujące kroki:

  • jeśli element jest liczbą, to przekazujemy go bezpośrednio na wyjście
  • jeśli element jest operatorem, to kładziemy go na stos, jednakże najpierw ze stosu zdejmujemy (i przekazujemy na wyjście) kolejno wszystkie operatory, których priorytet jest większy bądź równy priorytetowi operatora, którego chcemy położyć na stosie
  • jeśli element jest nawiasem otwierający, to kładziemy go na stos
  • jeśli element jest nawiasem zamykającym, to ze stosu zdejmujemy (i przekazujemy na wyjście) wszystkie elementy, aż do pierwszego nawiasu otwierającego. Przy czym nawiasy (zarówno otwierający i zamykający nie są przekazywane na wyjście).
  • na koniec wszystkie elementy pozostałe na stosie, przekazywane są do wyjścia.

Przykładowe wyrażenie:

(3 + 4) * 5

Zawartość stosu i wyjścia przedstawiać się będzie następująco:
( //nawias na stos
liczba 3 trafiła na wyjście
( + //plus na stos
liczba 4 trafiła na wyjście
) //nawias zamykający, więc zdejmujemy plus i nawias ze stosu (plus trafia na wyjście, nawias jest pomijany)
* //na pusty stos trafia operator mnożenia
liczba 5 trafia na wyjście
na koniec ze stosu zdejmujemy operator mnożenia

Na wyjściu pojawiały się kolejno:
3 4 + 5 *

Istniejące zadania

Nawiasy (V OIG - III etap (zawody próbne)

Program (IV OIG - I etap)

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License