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:

• Sprawdzenie, czy stos jest pusty – operacja empty zwraca true, jeśli stos nie zawiera żadnego elementu, w przeciwnym razie zwraca false
• Odczyt szczytu stosu – operacja top zwraca element (zwykle jest to wskaźnik) znajdujący się na szczycie stosu, sam element pozostaje wciąż na stosie.
• Zapis na stos – operacja push umieszcza na szczycie stosu nowy element.
• Usunięcie ze stosu – operacja pop usuwa ze szczytu stosu znajdujący się tam element.

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.

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

Wyjście:

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

Lista kroków:

bool empty(void)
{
  return !sptr;
}

Stos w tablicy – algorytm odczytu szczytu stosu

Wejście

Wyjście:

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

Lista kroków:

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

Stos w tablicy – algorytm zapisu na stos

Wejście

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:

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

Stos w tablicy – algorytm usuwania ze stosu

Wejście

Wyjście:

Ze szczytu stosu zostaje usunięty element.

Lista kroków:

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

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:

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:

• + – dodawanie
• - – odejmowanie
• * – mnożenie
• / – dzielenie

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++

#include <iostream>

using namespace std;

int main()
{
    double x;

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

#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:

Wyjście:

Wartość wyrażenia ONP na szczycie stosu S

Elementy pomocnicze:

Lista kroków:

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:

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:

Przed zaprojektowaniem algorytmu ustalamy co następuje:

• Symbole są zbudowane z pojedynczych liter. Chodzi tutaj o uproszczenie analizy wyrażenia. Gdy napotkamy literę, to traktujemy ją jako symbol.
• W wyrażeniu dozwolone są tylko operacje +, -, *, / i ^ (potęgowanie).
• Wyrażenie wejściowe musi być poprawne – algorytm nie sprawdza tego.
• Operacje posiadają priorytety zgodne z zasadami arytmetyki – najwyższy priorytet ma potęgowania, później mnożenie i dzielenie, a na końcu dodawanie i odejmowanie.
• Wyrażenie kończy się znakiem "=".

Algorytm przekształcania wyrażenia na postać ONP

Wejście:

symboliczne wyrażenie arytmetyczne

Wyjście:

wyrażenie ONP

Zmienne i funkcje pomocnicze:

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

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe