Poznaliśmy różne rodzaje zapisów wyrażeń arytmetycznych. Dowiedzieliśmy się, że najpopularniejszym z nich jest zapis infiksowy. Omówiliśmy notację polską (NP), w której operator jest zapisywany na początku wyrażenia, a także odwrotną notację polską (ONP). Poznamy teraz algorytm wykorzystywany podczas obliczania wartości wyrażenia zapisanego w ONP.

Kolejność działań w ONP

W ONP kolejnością wykonywania działań jest kolejność, w której pojawiają się liczby i operatory. Z tego powodu w notacji tej nie stosujemy nawiasów. ONP w dużej mierze bazuje na strukturze danych zwanej stosemstosstosem. Strukturę taką możemy sobie wyobrazić jako stos przedmiotów leżących jeden na drugim. Jeżeli dokładamy kolejny przedmiot, umieszczamy go na górze. Żeby dostać się do elementów znajdujących się niżej, musimy zdjąć te znajdujące się powyżej. Dlatego też ostatni element dodany do stosu będzie zdjęty jako pierwszy.

Obliczanie wartości wyrażenia w ONP

Aby obliczyć wartość wyrażenia zapisanego w ONP, po kolei pobieramy elementy wyrażenia. Jeżeli element jest liczbą, zostaje umieszczony na stosie. Natomiast jeżeli element jest operatorem, zdejmujemy dwa elementy ze stosu i wykonujemy na nich operację wskazaną przez operator. Otrzymany wynik umieszczamy na stosie. Po przejściu przez całe wyrażenie arytmetyczne na stosie zostaje tylko jedna liczba, która jest obliczonym wynikiem.

Przykład

Spróbujmy określić wartość wyrażenia: 3 5 + 2 4 * +.

Działanie programu zaczynamy z pustym stosem. Pierwszym elementem, jaki sprawdzamy, jest liczba 3.

Stos:

Wyrażenie: 3 5 + 2 4 * +

Ponieważ element 3 jest liczbą, zostaje umieszczony na stosie. Przechodzimy do kolejnego elementu.

Stos: 3

Wyrażenie: 5 + 2 4 * +

Kolejnym elementem jest $5$, czyli również liczba. Ją też umieszczamy na stosie.

Stos: 3 5

Wyrażenie: + 2 4 * +

Następnym elementem nie jest liczba, lecz operator dodawania. Zdejmujemy zatem ze stosu dwie liczby i dodajemy je do siebie. Wynik działania układamy na stosie.

Stos: 8

Wyrażenie: 2 4 * +

Sprawdzamy kolejny element. Tym razem jest nim liczba $2$, którą umieszczamy na stosie.

Stos: 8 2

Wyrażenie: 4 * +

Zaraz za nią znajduje się element $4$, który jako liczba również trafia na stos.

Stos: 8 2 4

Wyrażenie: * +

Kolejnym znakiem jest operator mnożenia, a więc zdejmujemy dwie górne liczby ze stosu i mnożymy je przez siebie. Iloczyn umieszczamy na stosie.

Stos: 8 8

Wyrażenie: +

Pozostaje ostatni element, który jest operatorem dodawania. Ponownie zdejmujemy dwie liczby ze stosu. Po dodaniu ich do siebie wynik umieszczamy na stosie.

Stos: 16

Wyrażenie:

Odczytaliśmy wszystkie elementy, a na stosie znajduje się tylko jedna liczba. Element ten jest obliczonym wynikiem wyrażenia – jest to 16.

Tworzenie stosu z wykorzystaniem tablicy w języku C++

W następnej sekcji zaprezentujemy implementację omówionego algorytmu w języku C++. Zanim jednak do niej przejdziemy, zastanówmy się, jak skonstruować stos, używając tablicy w języku C++. Najpierw zadeklarujemy tablicę służącą do przechowywania liczb. Potrzebna będzie też zmienna przechowująca indeks pierwszego wolnego elementu tablicy. Początkowo będzie ona miała wartość 0.

Umieszczając elementy na stosie, będziemy zapisywać je w miejscu wskazanym przez wspomniany indeks. Równocześnie musimy zwiększać wartość zmiennej przechowującej indeks. Jeżeli będziemy zdejmować element ze stosu, zwrócimy wartość ostatnio położoną oraz o indeksie o jeden mniejszym niż pierwszy wolny i zmniejszymy wartość zmiennej przechowującej indeks.

Słownik