Sposoby zapisywania wyrażeń arytmetycznych

Jak już wiemy, zapis infiksowyzapis infiksowyzapis infiksowy (w którym operator znajduje się między argumentami) nie jest jedyną postacią zapisu arytmetycznego. W przypadku zastosowania notacji polskiej na początku zapisywany jest operator, a dopiero później argumenty. Innymi słowy, działanie 3 + 3 w notacji polskiej przyjmuje postać + 3 3.

Istnieje również odwrotna notacja polska (ONPONPONP). W jej przypadku operator jest umieszczony na końcu, za argumentami. Działanie 3 + 3 w ONP zostanie zapisane jako 3 3 +.

Odwrotna notacja polska

ONP, podobnie jak zwykła notacja polska, jest metodą zapisu, w której nie używa się nawiasów. Są one zbędne – działania wykonuje się zawsze na dwóch elementach poprzedzających operator.

Dlaczego jednak w ogóle zajmujemy się odwrotną notacją polską? Sprawia ona wrażenie zupełnie nienaturalnej. Jesteśmy przecież przyzwyczajeni do klasycznej notacji arytmetycznej. Używamy jej w życiu codziennym – na przykład pisząc programy.

ONP odpowiada sposobowi, w jaki procesory przetwarzają informacje. Wykorzystywana jest przy tym struktura danych zwana stosem. Możemy sobie go wyobrazić jako zbiór przedmiotów ułożonych jeden na drugim (tak wygląda choćby stos książek). Jeżeli dokładamy do stosu kolejny przedmiot, trafia on na sam szczyt. Aby wyjąć element położony niżej, należy po kolei zdejmować przedmioty, zaczynając od góry. Innymi słowy, ostatni element dodany do stosu jest dostępny od razu, zaś do pierwszego dostaniemy się na końcu.

Algorytm obliczania wartości wyrażenia zapisanego w ONP jest bardzo prosty. Po kolei odczytujemy elementy wyrażenia. Jeżeli mamy do czynienia z liczbą, umieszczamy ją na stosie. Gdy elementem jest operator, zdejmujemy dwie liczby ze stosu, wykonujemy na nich działanie wskazane przez operator, a otrzymany wynik umieszczamy na stosie. Gdy będziemy tak postępować, po odczytaniu wszystkich elementów wrażenia arytmetycznego na stosie pozostanie tylko jedna liczba (obliczona wartość wyrażenia).

Opisany sposób wykonywania obliczeń ułatwia pracę projektantom procesorów. Pamiętajmy, że procesor nie „patrzy” na zapis arytmetyczny tak samo jak człowiek. Ludzki mózg jest zbudowany w ten sposób, że potrafi grupować argumenty i operatory zgodnie z ustaloną konwencją, np. najpierw wykonuje operacje zapisane wewnątrz pary nawiasów. Procesor także potrafiłby to zrobić, ale komplikowałoby to jego konstrukcję (i podnosiło cenę). O wiele prostsze (i tańsze) są układy, które albo zapisują dane na stosie, albo wykonują operacje na jego dwóch elementach.

Obliczanie wartości wyrażenia arytmetycznego

Spróbujmy obliczyć wartość wyrażenia zapisanego w ONP, np. 2 8 + 7 5 * +.

Obliczenia rozpoczynamy, mając pusty stos. Odczytujemy pierwszy element wyrażenia. Jest nim liczba 2. Zostaje ona umieszczona na stosie:

R19YwTaOHsIW1

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz blok z liczbą 2.
Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +. Od bloku z liczbą 2 wychodzi strzałka wskazująca na blok stosu zawierający liczbę 2.

Postąpiliśmy zgodnie z przedstawionym wcześniej algorytmem. Ponieważ 2 jest liczbą, powinna znaleźć się na stosie. Przechodzimy do kolejnego elementu. Jest nim liczba 8, a więc ją również umieszczamy na stosie.

R1TsPOuANiYDK

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 2, 8.
Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +. Od bloku z liczbą 8 wychodzi strzałka wskazująca na blok stosu zawierający liczbę 8.

Kolejnym elementem jest operator dodawania. Zdejmujemy zatem ze stosu dwie liczby i dodajemy je do siebie:

R1RJbFoI0mfpz

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 2, 8. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Od bloków stosu: 8, 2 oraz od bloku poniżej z wartością: + wychodzą strzałki wskazujące na równoległobok z wpisanym równaniem: 8*2=10.

Otrzymaną sumę umieszczamy na stosie:

RutNjHnJcKy9U

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz blok z liczbą 10. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Powyżej znajduje się równoległobok z wpisanym równaniem: 8+2=10, od którego wychodzi strzałka wskazująca na blok stosu z liczbą 10.

Sprawdzamy kolejny element wyrażenia. Jest nim liczba 7, która trafia na szczyt stosu:

R7JPao7MbZPKc

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 10, 7. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +. Od bloku z liczbą 7 wychodzi strzałka wskazująca na blok stosu zawierający liczbę 7.

Tuż za nią znajduje się liczba 5, ją również umieszczamy na stosie:

R5fR59vzLVYxQ

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 10, 7, 5. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Od bloku z liczbą 5 wychodzi strzałka wskazująca na blok stosu zawierający liczbę 5.

Kolejnym elementem jest operator mnożenia. Pobieramy zatem ze stosu dwie liczby i mnożymy je przez siebie:

RC36qCfi3iWGK

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 10, 7, 5. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Od bloków stosu: 7, 5 oraz od bloku poniżej z wpisem: * wychodzą strzałki wskazujące na równoległobok z wpisanym równaniem: 5*7=35.

Otrzymany iloczyn trafia na stos:

RWzDMizrHt6Xq

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 10, 35. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Powyżej znajduje się równoległobok z wpisanym równaniem: 5*7=35, od którego wychodzi strzałka wskazująca na blok stosu z wartością 35.

Pozostał ostatni element wyrażenia: jest on operatorem dodawania. Odczytujemy dwie liczby pozostające jeszcze na stosie i dodajemy je do siebie:

R1aliJQnhtSe9

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz bloki z wartościami: 10, 35. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Od bloków stosu: 10, 35 oraz od bloku poniżej z wartością: + wychodzą strzałki wskazujące na równoległobok z wpisanym równaniem: 35+10=45.

Sumę umieszczamy na stosie:

R376zNX9ArRSA

Ilustracja przedstawia żółtą podstawę, na której znajduje się napis STOS oraz blok z wartością: 45. Poniżej znajdują się bloki z wartościami: 2, 8, +, 7, 5, *, +.
Powyżej znajduje się równoległobok z wpisanym równaniem: 35+10=45, od którego wychodzi strzałka wskazująca na blok stosu z wartością 45.

Odczytaliśmy już wszystkie elementy wyrażenia, postępując zgodnie z przedstawionym wcześniej algorytmem. Na stosie znajduje się tylko jedna liczba. Jest ona obliczona wartością wyrażenia. A zatem: (2 + 8) + (7 * 5) = 2 8 + 7 5 * + = 45.

W następnej sekcji zajmiemy się przełożeniem na język Java algorytmu obliczania wartości wyrażeń zapisanych z wykorzystaniem ONP.  Zastanówmy się jednak najpierw, jak utworzyć stos.

Okazuje się, że nie jest to trudne. Rozpoczniemy od zdefiniowania tablicy, która będzie pełnić funkcję stosu. Zdefiniujemy również zmienną przechowującą indeks pierwszego niezapełnionego miejsca w tablicy (początkowo będzie nim oczywiście 0).

Umieszczając elementy na stosie, będziemy zapisywać je na pierwszym wolnym miejscu. Jego indeks odczytamy ze zdefiniowanej wcześniej zmiennej, a następnie zwiększymy jej wartość (ponieważ pierwsze wolne miejsce w tablicy zostało właśnie zajęte). Kiedy natomiast będziemy zdejmować liczbę ze stosu, zmniejszymy wartość zmiennej przechowującej indeks wierzchołka stosu.

Możemy już zająć się pisaniem programu obliczającego wartości wyrażeń przedstawionych z zastosowaniem odwrotnej notacji polskiej.

Słownik