Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Stos

Stos (ang. stack) jest jedną z częściej używanych struktur danych w programowaniu - stosuje go olbrzymia liczba algorytmów. Na stosie dane umieszczamy w sposób sekwencyjny. Pobieramy je również ze stosu sekwencyjnie (tzn. jedna za drugą), jednakże w kierunku odwrotnym do wpisania. Dobrym przykładem stosu może być zwykły stos książek lub czasopism - kładziemy je po kolei jedne na drugich. Ściągamy te, które są na wierzchu.

Do prostej realizacji stosu potrzebujemy dwóch rzeczy:

- tablicy, która będzie przechowywała dane umieszczone na stosie,

- zmiennej, w której będziemy przechowywali pozycję zapisu na stos. Zmienna ta nosi nazwę wskaźnika stosu (ang. stack pointer).

Przed rozpoczęciem pracy ze stosem wskaźnik stosu powinien być zainicjowany na 0. Umówmy się, że wskaźnik stosu zawiera numer komórki tablicy, w której możemy umieścić dane. Pierwszą komórką stosu jest komórka o indeksie 0, dlatego właśnie zerujemy wskaźnik stosu, aby wskazywał na tę komórkę.

Operacja zapisu na stos będzie polegała na umieszczeniu danej w komórce, którą adresuje wskaźnik stosu, po czym zwiększamy o jeden stan wskaźnika. W wyniku będzie on wskazywał komórkę o indeksie 1. To następne miejsce, gdzie na stosie można umieścić nową daną.

Zapis danych na stos

W miarę zapisu danych stos "rośnie" w górę. Liczbę danych przechowywanych na stosie zawiera wskaźnik stosu. Na powyższym obrazku wskaźnik stosu kończy z wartością 2, co oznacza, iż stos przechowuje dwie dane. Wskaźnik stosu wskazuje na komórkę o indeksie 2, która nie zawiera danych. Stos jest pusty wtedy, gdy wskaźnik stosu ma wartość 0 (tak było przed wpisaniem danych).

Operacja odczytu danej ze stosu (który musi coś zawierać) polega na zmniejszeniu wskaźnika stosu o 1. Wtedy będzie on wskazywał komórkę, w której ostatnio umieściliśmy dane. Komórkę tę odczytujemy. Po odczycie komórkę możemy potraktować jako pustą.

Odczyt danych ze stosu

Przy odczycie danych stos "maleje" w dół. Operację odczytywania danych można prowadzić, aż do osiągnięcia przez wskaźnik stosu wartości 0. Wtedy stos jest pusty i dalszy odczyt nie ma sensu.

Podsumujmy:

stos[n] - tablica o n komórkach, w której realizujemy stos
ws - wskaźnik stosu

Inicjalizacja

ws = 0;

Zapis na stos

stos[ws++] = dane;

Odczyt ze stosu

dane = stos[--ws];

Poniższy program demonstruje prosty stos w tablicy. Zapisuje on na stosie 5 pseudolosowych liczb, a następnie je odczytuje ze stosu.

// Przykładowy stos
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int stos[5];
    int ws = 0;   // wskaźnik stosu

    srand(time(NULL)); // inicjujemy generator liczb pseudolosowych

    // zapisujemy na stos 5 przypadkowych liczb

    while(ws < 5)
    {
        int dane = rand() % 100;  // liczby pseudolosowe 0..99

        cout << "Zapis  ws = " << ws << " : " << dane << endl;

        stos[ws++] = dane;
    }

    cout << endl;

    // odczytujemy dane ze stosu

    while(ws > 0)
    {
        int dane = stos[--ws];

        cout << "Odczyt ws = " << ws << " : " << dane << endl; 
    }

    return 0;
}

ONP - Odwrotna Notacja Polska

ONP (ang. RPN - Reverse Polish Notation) jest sposobem zapisu wyrażeń arytmetycznych bez stosowania nawiasów, w którym symbol operacji występuje po argumentach. Poniżej podajemy przykłady wyrażeń w ONP:

ONP jest powszechnie stosowana w kompilatorach języków HLL do obliczania wartości wyrażeń arytmetycznych. Spowodowane jest to prostotą obliczeń w porównaniu do zwykłej notacji z nawiasami. Algorytm obliczania wartości wyrażenia ONP wykorzystuje stos do składowania wyników pośrednich. Zasada pracy tego algorytmu jest bardzo prosta:

Z wejścia odczytujemy kolejne elementy wyrażenia. Jeśli element jest liczbą, zapisujemy ją na stosie. Jeśli element jest operatorem, ze stosu zdejmujemy dwie liczby, wykonujemy nad nimi operację określoną przez odczytany element, wynik operacji umieszczamy z powrotem na stosie. Jeśli element jest końcowym znakiem '=', to na wyjście przesyłamy liczbę ze szczytu stosu i kończymy. Inaczej kontynuujemy odczyt i przetwarzanie kolejnych elementów.

Dla przykładu obliczmy tą metodą wartość wyrażenia 7 3 + 5 2 - 2 ^ * =

Algorytm obliczania wartości wyrażenia w ONP

Dane wejściowe

we  - wyrażenie ONP, które można odczytywać poszczególnymi elementami. Na końcu wyrażenia znajduje się znak '='

Dane wyjściowe

wartość wyrażenia ONP

Dane pomocnicze

stos  - przechowuje wyniki pośrednie
el    - element odczytany z we
a,b  - przechowuje dane ze stosu
w   - wynik operacji arytmetycznej

Lista kroków

Przykładowe dane dla programu

Uwaga: dane liczbowe nie mogą być ujemne. Dozwolone operatory to +, -, *, / i ^.  Program nie ma zaimplementowanej obsługi błędów. Wprowadzane wyrażenie ONP musi być poprawne składniowo, inaczej program nie będzie zwracał poprawnych wyników.

77 3 + 5 2 - * =

// Obliczanie wartości wyrażenia w ONP
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int  stos[256], ws = 0;
    int  a, b, w;
    char el[256];

    do
    {
        cin >> el;

        if(el[0] >= '0' && el[0] <= '9')
        {
            a = b = 0;
            do a = 10 * a + el[b++] - 48; while(el[b]);
            stos[ws++] = a;
        }
        else if(el[0] == '=') cout << stos[--ws] << endl;
        else
        {
            b = stos[--ws]; a = stos[--ws];

            switch(el[0])
            {
                case '+': w = a + b; break;
                case '-': w = a - b; break;
                case '*': w = a * b; break;
                case '/': w = a / b; break;
                case '^': w = 1;
                          while(b--) w *= a;
                          break;
            }

            stos[ws++] = w;
        }
    } while(el[0] != '=');

    return 0;
}

Przekształcanie wyrażeń na ONP

Algorytm obliczania wartości wyrażenia ONP wykorzystywał stos do składowania wyników pośrednich. Algorytm przekształcania wyrażeń arytmetycznych na ONP będzie wykorzystywał stos do przechowywania operatorów i nawiasów. Ponieważ są to znaki, stos operatorów będzie zrealizowany w postaci tablicy znakowej.

Operatory arytmetyczne posiadają różne priorytety (różną wartość). Jeśli w wyrażeniu arytmetycznym spotka się kilka operatorów, to operatory z wyższym priorytetem będą wykonane najpierw:

2 + 5 * 3 - 18 / 3 ^ 2 = 2 + 5 * 3 - 18 / 9 = 2 + 15 - 2 = 15

Operatory o równym priorytecie są wykonywane z lewa na prawo

Określmy priorytety operatorów następująco:

Operacje potęgowania mają najwyższy priorytet - będą wykonywane przed innymi operacjami. Najniższy priorytet mają operacje dodawania i odejmowania - będą wykonywane po wszystkich innych działaniach.

Zasada przekształcania wyrażenia na ONP jest następująca:

Czytamy z wejścia element. Dalsze postępowanie zależy od rodzaju elementu:

1. Liczba - przesyłamy ją na wyjście.

2. Operator - przesyłamy ze stosu na wyjście wszystkie operatory o priorytecie wyższym lub równym odczytanemu operatorowi. Operator dopisujemy do stosu.

3. ( - nawias otwierający zawsze dopisujemy do stosu.

4. ) - przesyłamy ze stosu na wyjście wszystkie operatory aż do napotkania nawiasu otwierającego. Nawias ten usuwamy ze stosu.

5. = - przesyłamy ze stosu na wyjście wszystkie pozostałe na nim operatory wraz ze znakiem '=' i kończymy algorytm

Wracamy na początek do odczytu elementu wyrażenia.

Dla przykładu obliczmy tą metodą wartość wyrażenia ( 15 - 3 ) ^ ( 3 + 2 ) * 6 /  3 =

Algorytm przeliczania na ONP

Dane wejściowe

we  - wyrażenie arytmetyczne zakończone znakiem =

Dane wyjściowe

wy - postać ONP wyrażenia wejściowego

Dane pomocnicze

stos  - przechowuje operatory
el    - element odczytany z we

Lista kroków

Przykładowe dane dla programu

Uwaga: dane liczbowe nie mogą być ujemne. Dozwolone operatory to +, -, *, /, ^ oraz nawiasy okrągłe. Każdy element wyrażenia musi być oddzielony spacją od elementów sąsiednich. Program nie posiada obsługi błędów i wyrażenie wejściowe musi być poprawne.

( ( 5 - 2 ) ^ ( 3 + 1 ) / ( 2 + 1 ) + 12 ) * 21 =

// Przeliczanie wyrażenia na ONP
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    char stos[256],el[256];
    int ws = 0;

    do
    {
        cin >> el;

        if(el[0] >= '0' && el[0] <= '9') cout << el << " ";
        else
            switch(el[0])
            {
                case '+': ;
                case '-': while(ws && stos[ws - 1] != '(') cout << stos[--ws] << " ";
                          stos[ws++] = el[0];
                          break;
                case '*': ;
                case '/': while(ws && stos[ws - 1] != '(' &&
                                      stos[ws - 1] != '+' &&
                                      stos[ws - 1] != '-') cout << stos[--ws] << " ";
                          stos[ws++] = el[0];
                          break;  
                case '^': while(ws && stos[ws - 1] == '^') cout << stos[--ws] << " ";
                          stos[ws++] = el[0];
                          break;
                case '(': stos[ws++] = '(';
                          break;
                case ')': while(stos[ws - 1] != '(') cout << stos[--ws] << " ";
                          ws--;
                          break;
                case '=': while(ws) cout << stos[--ws] << " ";
                          cout << " =\n\n";
                          break;
            }

    } while(el[0] != '=');

    return 0;
}

Dla ambitnych: na podstawie tych dwóch programów stwórz program, który oblicza wartość wyrażeń arytmetycznych zawierających operatory +, -, *, /, ^ oraz nawiasy okrągłe.

Dla myślących: czy zadanie to da się zrealizować bez pisania jakiegokolwiek nowego programu? (wskazówka - poczytaj o przekierowywaniu wejścia/wyjścia programów - ang. I/O redirection).

---

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

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

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