ONP a zapis postfiksowy

Rozróżniamy trzy sposoby zapisu wyrażeń arytmetycznych: zapis prefiksowy,zapis prefiksowyzapis prefiksowy, zapis infiksowyzapis infiksowyzapis infiksowy i zapis postfiksowyzapis postfiksowyzapis postfiksowy.

Najpowszechniejszą notacją jest notacja infiksowa, w której operator jest umieszczany między operandamioperandoperandami.

W innych e‑materiałach omawialiśmy różne sposoby zapisywania wyrażeń arytmetycznych. Należy do nich tzw. odwrotna notacja polska – więcej informacji na jej temat znajduje się w e‑materiale Odwrotna notacja polskaP10WrdFSpOdwrotna notacja polska.

ONP jest zapisem postfiksowym, co oznacza, że operator umieszczany jest po operandach, np. zapis w ONP $5\;7\;\ast$ odpowiada infiksowemu zapisowi $7\;\ast\;5$.

ONP – wykonanie przykładowego działania

Zapis: $2\;9\;\ast\;5\;+$ odczytujemy:

1. Jako jeden operand weźmy liczbę 2.

2. Jako drugi operand weźmy liczbę 9.

3. Pomnóżmy przez siebie liczby 9 i 2.

4. Zapiszmy w miejscu operandów (czyli liczb 9 i 2) i znaku działania (w tym przypadku znaku mnożenia) wynik wykonanego obliczenia. Otrzymujemy: $185+$.

5. Jako pierwszy operand kolejnego działania weźmy liczbę 18.

6. Jako drugi operand weźmy liczbę 5.

7. Do liczby 18 dodajmy liczbę 5.

8. Wynik działania $2\;9\;\ast\;5\;+$ jest równy 23 (ponieważ $9\ast 2=18$ i $18+5=23$).

Po wykonaniu tego działania możemy dojść do wniosku, że zaprezentowane wyrażenie arytmetyczne można zapisać za pomocą klasycznej notacji w postaci: $2\ast 9+5$.

1. Jako pierwszy rozważany operand weźmy liczbę 11.

2. Następnym operandem będzie liczba 3.

3. Dodajmy liczby 3 oraz 11.

4. Zapiszmy wynik sumy w miejscu operandów oraz znaku wykonanego obliczenia: $14\;6\;\ast\;4\;1\;+\;-$.

5. Jako jeden operand weźmy liczbę 14.

6. Jako drugi operand weźmy liczbę 6.

7. Pomnóżmy przez siebie liczby 6 i 14.

8. Wynik mnożenia zapiszmy w miejscu operandów oraz znaku wykonanego obliczenia. Otrzymujemy: $84\;4\;1\;+\;-$.

9. Jako pierwszy operand weźmy liczbę 84.

10. Jako drugi operand weźmy liczbę 4.

11. Ponieważ jako kolejna jest zapisana liczba, a nie znak wykonywanego działania, odłóżmy operand pobrany jako pierwszy, czyli wartość 84, do rozważenia później i weźmy jako pierwszy operand liczbę 4, a jako drugi operand weźmy liczbę 1.

12. Dodajmy do siebie liczby 4 i 1.

13. Sumę tych liczb zapiszmy w miejscu operandów oraz znaku wykonanego obliczenia: $84\;5\;–$.

14. Jako jeden operand weźmy liczbę 84.

15. Jako drugi operand weźmy liczbę 5.

16. Odejmijmy od 84 liczbę 5.

17. Wynik działania $11\;3\;+\;6\;\ast\;4\;1\;+\;-$ jest równy 79:

    • $11+3=14$

    • $14\;\ast\;6\;=\;84$

    • $4\;+\;1\;=\;5$

    • $84\;-\;5\;=\;79$.

Tym razem omówimy algorytm pozwalający obliczyć wartość wyrażenia zapisanego w odwrotnej notacji polskiej.

Algorytm obliczania wartości wyrażenia w ONP

Algorytm wykorzystywany do obliczania wartość wyrażenia zapisanego w odwrotnej notacji polskiej odpowiada sposobowi, w jaki procesory przetwarzają informacje.

Po kolei odczytujemy elementy wyrażenia. Jeżeli okaże się, że element jest liczbą, umieszczamy ją na stosiestosstosie. W przypadku gdy element jest operatorem, zdejmujemy dwie liczby ze stosu, wykonujemy na nich działanie odpowiadające operatorowi, a wynik umieszczamy na stosie. Przy wykonywaniu działań istotna jest kolejność operandów. Pierwszym (lewym) operandem jest wartość odczytana ze stosu jako druga, natomiast wartość odczytana ze stosu jako pierwsza jest drugim (prawym) operandem. Po odczytaniu całego wyrażenia arytmetycznego na stosie zostanie tylko jedna liczba – to właśnie wartość wyrażenia.

Pseudokod obliczania wartości wyrażenia w ONP

funkcja oblicz(ciąg wyrażeń):
	dopóki ciąg się nie skończył, wykonuj:
    	wyrażenie ← kolejna wartość odczytana z ciągu
        jeżeli wyrażenie jest liczbą:
        	odłóż wyrażenie na stosie
        jeżeli wyrażenie jest operatorem:
        	a ← odczytaj liczbę ze stosu
            b ← odczytaj liczbę ze stosu
            wynik ← zapisz wynik działania (b wyrażenie a)
            odłóż wynik działania na stosie
	Zwróć pozostałą na stosie wartość

Sposób działania algorytmu pokażemy na przykładzie: 9 3 + 6 6 * +.

Tworzymy stos, który jest początkowo pusty.

Stos:

Wyrażenie: 9 3 + 6 6 * +

Odczytujemy pierwszy element wyrażenia. Jest nim liczba 9. Ponieważ pierwszy element jest liczbą; zostaje ona umieszczona na stosie. Przechodzimy do kolejnego elementu.

Stos: 9

Wyrażenie: 3 + 6 6 * +

Kolejnym elementem jest liczba 3; ją także umieszczamy na stosie.

Stos: 9 3

Wyrażenie: + 6 6 * +

Następnym elementem jest operator dodawania. Zdejmujemy ze stosu dwie liczby i dodajemy je do siebie. Pierwszym (lewym) operandem działania jest liczba zdjęta ze stosu jako druga, czyli w tym przypadku 9, do którego dodajemy drugi operand: 3.

Wynik operacji umieszczamy na stosie.

Stos: 12

Wyrażenie: 6 6 * +

Sprawdzamy kolejny element. Jest nim liczba 6. Umieszczamy ją na stosie.

Stos: 12 6

Wyrażenie: 6 * +

Następnym elementem jest także liczba 6; trafia ona na szczyt stosu.

Stos: 12 6 6

Wyrażenie: * +

Kolejnym znakiem jest operator mnożenia. Zdejmujemy dwie liczby ze stosu i mnożymy je przez siebie. Zgodnie z algorytmem pierwszym operandem jest liczba zdjęta ze stosu jako druga (w tym przypadku wartość obu operandów jest taka sama).

Iloczyn umieszczamy na stosie.

Stos: 12 36

Wyrażenie: +

Pozostał ostatni element wyrażenia. Jest to operator dodawania. Zdejmujemy dwie liczby ze stosu i dodajemy je do siebie. Tak jak w poprzednich działaniach, pierwszym operandem jest liczba zdjęta za stosu jako druga (czyli w tym przypadku: 12), do której zostaje dodana wartość wcześniej odczytana ze stosu (w tym przypadku: 36)

Sumę umieszczamy na stosie.

Stos: 48

Wyrażenie:

Odczytaliśmy już wszystkie elementy wyrażenia. Na stosie znajduje się tylko jedna liczba. Wartość całego wyrażenia wynosi 48.

Słownik