Stos

Stos (ang. stack) jest sekwencyjną strukturą danych. Najprościej możemy go sobie wyobrazić jako stos książek na biurku. Nowe książki układamy na szczycie stosu (ang. stack top), wtedy stos rośnie w górę.

 

 

Ze stosu pobieramy książki znajdujące się na samej górze, wtedy stos maleje. Zwróć uwagę, że książki zawsze zdejmujesz ze stosu w kolejności odwrotnej do ich umieszczania – jako pierwszą zdejmiesz ostatnią książkę na stosie.

 

 

Wracając do świata komputerów, stos jest taką strukturą danych, z której odczytujemy elementy w kolejności odwrotnej do ich wstawiania. Struktura ta nosi nazwę LIFO (ang. Last In – First Out – wszedł ostatni, a wyszedł pierwszy).

Rozróżniamy następujące operacje dla stosu:

Stosy możemy realizować za pomocą tablic lub list jednokierunkowych. Realizacja tablicowa jest bardzo prosta i szybka. Stosujemy ją wtedy, gdy dokładnie wiemy, ile maksymalnie elementów będzie przechowywał stos – jest to potrzebne do przygotowania odpowiednio pojemnej tablicy na elementy stosu. Realizacja za pomocą listy jednokierunkowej jest przydatna wtedy, gdy nie znamy dokładnego rozmiaru stosu – listy dostosowują się dobrze do obszarów wolnej pamięci.

 

Tablica jako stos

Do utworzenia stosu w tablicy potrzebujemy dwóch zmiennych. Pierwszą z nich będzie tablica, która przechowuje umieszczone na stosie elementy. Druga zmienna sptr służy do zapamiętywania pozycji szczytu stosu i nosi nazwę wskaźnika stosu (ang. stack pointer). Umawiamy się, że wskaźnik stosu zawsze wskazuje pustą komórkę tablicy, która znajduje się tuż ponad szczytem stosu:

 

Po utworzeniu tablicy zmienna sptr musi zawsze być zerowana. Stos jest pusty, gdy sptr wskazuje początek tablicy, czyli komórkę o indeksie zero. Ta własność jest wykorzystywana w operacji empty. Stos jest pełny, gdy sptr ma wartość równą liczbie komórek tablicy. W takim przypadku na stosie nie można już umieszczać żadnych dalszych danych. gdyż trafiłyby poza obszar zarezerwowany na tablicę.

 

Stos w tablicy – algorytm sprawdzania, czy stos jest pusty

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
Wyjście:

True, jeśli na stosie nie ma żadnego elementu, inaczej false

Lista kroków:
K01 Jeśli sptr = 0, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

bool empty(void)
{
  return !sptr;
}

 

Stos w tablicy – algorytm odczytu szczytu stosu

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
n  – rozmiar tablicy
S  – tablica przechowująca stos
Wyjście:

Zawartość szczytu stosu lub wartość specjalna, jeśli stos jest pusty.

Lista kroków:
K01 Jeśli sptr = 0, to zakończ z wynikiem wartość specjalną
K02: Zakończ z wynikiem S[sptr - 1]

 

typ_danych top(void)
{
  if(sptr) return S[sptr - 1);
  return wartość_specjalna
}

 

Stos w tablicy – algorytm zapisu na stos

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
n  – rozmiar tablicy
S  – tablica przechowująca stos
v  – zapisywana wartość
Wyjście:

Na stosie zostaje zapisana wartość v, jeśli jest na to miejsce. W przeciwnym razie v nie będzie zapisane.

Lista kroków:
K01 Jeśli sptr = n, to zakończ ; stos jest pełny i nie ma miejsca na nową wartość
K02: S[sptr] ← v ; umieszczamy v ponad szczytem stosu
K03: sptrsptr + 1 ; zwiększamy wskaźnik stosu
K04: Zakończ  

 

void push(typ_danych v)
{
  if(sptr < n) S[sptr++] = v;
}

 

Stos w tablicy – algorytm usuwania ze stosu

Wejście
sptr    zmienna przechowująca wskaźnik stosu tablicy
S  – tablica przechowująca stos
Wyjście:

Ze szczytu stosu zostaje usunięty element.

Lista kroków:
K01 Jeśli sptr > 0, to sptrsptr - 1 ; jeśli stos coś zawiera, to usuwamy element na szczycie stosu
K02: Zakończ  

 

void pop(void)
{
  if(sptr) sptr--;
}

 

ONP – obliczanie wartości wyrażenia

Odwrotną notację polską ONP (ang. RPN – Reverse Polish Notation), zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów. W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

 

2 + 2     6 - 4     3 * 5     12 / 3

 

Operatory posiadają priorytety, czyli "ważność". Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

 

3 + 5 * 2 = 3 + 10 = 13

 

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

 

(3 + 5) * 2 = 8 * 2 = 16

 

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

 

2 2 +     6 4 -     3 5 *     12 3 /

 

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

 

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

 

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

 

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

 

Przykład:

 

Wyrażenie ONP Element Operacja Stos
 3  5  2  *  +     ---
 3  5  2  *  +  3  na stos

3
---

 3  5  2  *  +  5  na stos

5
3
---

 3  5  2  *  +  2  na stos

2
5
3
---

 3  5  2  *  +  * 

pobierz 2 i 5
mnóż 5 * 2
wynik na stos

10
3
---

 3  5  2  *  +  + 

pobierz 10 i 3
dodaj 3 + 10
wynik na stos

13
---

 

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

Wyrażenie musi być poprawne – algorytm nie sprawdza jego poprawności.

Każdy element będzie wprowadzany w osobnym wierszu – w ten sposób pozbędziemy się problemu analizowania tekstu pod kątem zawartości w nim liczb i operatorów. W rzeczywistości wyrażenie zawarte w wierszu zostałoby najpierw rozbite na elementy składowe – liczby i operatory – a następnie elementy te zostałyby użyte do obliczenia wartości wyrażenia wg naszego algorytmu.

Liczby muszą mieć postać akceptowaną przez dany język programowania.

Ostatnim elementem wyrażenia jest znak "=". Powoduje on zakończenie obliczeń i wyprowadzenie wyniku ze stosu.

W algorytmie będziemy musieli rozpoznawać, czy wprowadzony element jest liczbą, czy też operatorem lub znakiem "=". W języku C++ można to zrobić następująco:

 

C++

Tutaj wykorzystuje się najczęściej strumienie. Wykorzystujemy własność strumienia, który przy złej konwersji daje wartość 0. Wypróbuj poniższy program dla strumienia cin:

 

#include <iostream>

using namespace std;

int main()
{
    double x;

    cout << (cin >> x) << endl;
    return 0;
}
 

Program odczytuje ze strumienia cin ciąg znaków i stara się je zamienić na liczbę zmiennoprzecinkową dla zmiennej x. Jeśli konwersja się powiedzie, to operacja (cin >> x) zwróci jakąś wartość różną od zera. Jeśli ciągu znaków nie da się zamienić na liczbę, to operacja zwróci wartość 0 (w programie wpisz wartość poprawną, np. 12.54, a następnie niepoprawną, np. ABC – za pierwszym razem otrzymasz coś różnego od zera, a za drugim zero). Jeśli operacje takie wykonujemy w pętli, to należy wyzerować stan znaczników błędów strumienia za pomocą funkcji cin.clear() – inaczej dostaniemy poprzednią wartość błędu.

Na tym prostym fakcie oprzemy rozpoznawanie, czy wprowadzony łańcuch tekstu reprezentuje liczbę, czy nie. Jako strumień wykorzystamy strumień łańcuchowy. Będzie nam potrzebny plik nagłówkowy sstream, który definiuje klasy strumieni łańcuchowych.

 

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    double x;
    stringstream ss; // strumień łańcuchowy
    string s;        // łańcuch;

    while(true)
    {
      cin >> s;        // czytamy łańcuch znaków
      ss.str("");      // usuwamy wszelki tekst ze strumienia
      ss.clear();      // czyścimy błędy konwersji z poprzednich wywołań
      ss << s;         // odczytany łańcuch umieszczamy w strumieniu
      if(ss >> x)      // konwertujemy na liczbę i sprawdzamy, czy konwersja była poprawna
        cout << "LICZBA";
      else
        cout << "NIE LICZBA";
      cout << endl << endl;
    }
    return 0;
}

 

Algorytm obliczania wartości wyrażenia ONP

Wejście:
S    stos liczb zmiennoprzecinkowych

Kolejne elementy wyrażenia odczytujemy ze standardowego wejścia

Wyjście:

Wartość wyrażenia ONP na szczycie stosu S

Elementy pomocnicze:
e  – przechowuje odczytaną informację z wejścia jako łańcuch tekstowy
v1, v2  –  przechowują argumenty operacji
Lista kroków:
K01: Czytaj e ; odczytujemy kolejne elementy wyrażenia ONP
K02: Jeśli e = "=", to zakończ ; znak = kończy wyrażenie ONP
K03: Jeśli e jest liczbą, to idź do K09 ; liczby umieszczamy na stosie
K04: v2 ← S.top()
S.pop()
; pobieramy ze stosu argumenty operacji
K05: v1 ← S.top()
S.pop()
 
K06: Wykonaj operację na v1 i v2 zgodnie z zawartością e.
Wynik umieść w v1
; wykonujemy obliczenia zgodnie ze znakiem operatora
K07: S.push(v1) ; wynik trafia na stos
K08: Idź do K01 ; kontynuujemy przetwarzanie wyrażenia
K09: Przekształć e na liczbę w v1  
K10: Idź do K07 ; liczbę umieszczamy na stosie

 

ONP – przeliczanie na ONP

W wyrażeniu symbolicznym zamiast wartości liczbowych występują symbole:  (a + b) * c

Gdy obliczaliśmy wartość wyrażenia ONP, stos był używany do przechowywania wyników częściowych obliczeń – czyli był to stos liczbowy. Przy konwersji wyrażenia arytmetycznego na postać ONP również wykorzystujemy stos, jednakże tutaj będzie on przechowywał nie liczby, a operatory. Zasada jest następująca:

 

Wyrażenie arytmetyczne odczytujemy od strony lewej do prawej.
  1. Jeśli dojdziemy do końca wyrażenia, to ze stosu operatorów pobieramy operatory i przenosimy je kolejno na wyjście aż do wyczyszczenia stosu. Algorytm kończymy.
  2. Jeśli odczytanym elementem jest symbol zmiennej, to przenosimy go na wyjście.
  3. Jeśli odczytanym elementem jest nawias otwierający, to umieszczamy go na stosie.
  4. Jeśli odczytanym elementem jest nawias zamykający, to ze stosu przesyłamy na wyjście wszystkie operatory, aż do napotkania nawiasu otwierającego, który usuwamy ze stosu.
  5. Jeśli odczytanym elementem jest operator, to ze stosu na wyjście przesyłamy wszystkie operatory o priorytecie wyższym od priorytetu odczytanego operatora. Po tej operacji operator umieszczamy na stosie.
  6. Kontynuujemy od początku z następnym elementem.

 

Przykład:

 

Wyrażenie Element Operacja Stos Wyjście
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =  start   ---  
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
---

 
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   a

na wyjście

(
---

 a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
---

a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   b

na wyjście

+
(
---

a  b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   *

na stos

 * 
+
(
---

a b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   c

na wyjście

*
+
(
---

a b  c
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   -

ze stosu na wyjście
na stos

-
+
(
---

a b c *
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   d

na wyjście

-
+
(
---

a b c *  d
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   )

ze stosu na wyjście
ze stosu na wyjście
usuń ze stosu

---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   /

na stos

 / 
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
/
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   e

na wyjście

(
/
---

a b c * d - +  e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
/
---

a b c * d - + e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   f

na wyjście

+
(
/
---

a b c * d - + e  f
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )   )

ze stosu na wyjście
usuń ze stosu

/
---

a b c * d - + e f +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  koniec

ze stosu na wyjście

---

a b c * d - + e f + /

 

Przed zaprojektowaniem algorytmu ustalamy co następuje:

 

Algorytm przekształcania wyrażenia na postać ONP

Wejście:

symboliczne wyrażenie arytmetyczne

Wyjście:

wyrażenie ONP

Zmienne i funkcje pomocnicze:
S  – stos operatorów
c  –  znak odczytany z wejścia
p(c)  –  funkcja zwracająca priorytet:
(    = 0
+ - = 1
* /  = 2
^    = 3
Lista kroków:
K01: Utwórz pusty stos S  
K02: Czytaj c ; odczytujemy znak z wejścia
K03: Jeśli c ≠ '=', to idź do K08 ; sprawdzamy, czy koniec wyrażenia
K04: Dopóki S.empty() = false, wykonuj K05...K06  
K05:     Pisz S.top() ; na wyjście przesyłamy operatory ze stosu
K06:     S.pop() ; przesłany operator usuwamy ze stosu
K07: Zakończ  
K08: Jeśli c ≠ '(', to idź do K11 ; sprawdzamy, czy mamy nawias otwierający
K09: S.push('(') ; nawias otwierający umieszczamy na stosie
K10: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K11: Jeśli c ≠ ')', to idź do K17 ; sprawdzamy, czy mamy nawias zamykający
K12: Dopóki S.top() ≠ '(', wykonuj K13...K14  
K13:     Pisz S.top() ; ze stosu przesyłamy na wyjście operatory
K14:     S.pop() ; aż do napotkania nawiasu otwierającego
K15: S.pop() ; usuwamy ze stosu nawias otwierający
K16: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K17: Jeśli c ≠ operator, to idź do K23 ; sprawdzamy, czy mamy operator
K18: Dopóki S.empty() = false p(S.top()) > p(c), wykonuj K19...K20  
K19:     Pisz S.top() ; na wyjście przesyłamy ze stosu operatory
K20:     S.pop() ; o wyższych priorytetach
K21: S.push(c) ; operator umieszczamy na stosie
K22: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K23: Pisz c ; z przesyłamy na wyjście
K24: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.