Algorytm obliczania wartości wyrażenia ONP

ONP – wykonanie przykładowego działania

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

Jako pierwszy operand weźmy liczbę 2.
Jako drugi operand weźmy liczbę 9.
Pomnóżmy przez siebie liczby 9 i 2.
Zapiszmy w miejscu operandów (czyli liczb 9 i 2) i znaku działania (w tym przypadku znaku mnożenia) wynik wykonanego obliczenia. Otrzymujemy: $18 5 +$ .
Jako pierwszy operand kolejnego działania weźmy liczbę 18.
Jako drugi operand weźmy liczbę 5.
Do liczby 18 dodajmy liczbę 5.
Wynik działania $2\;9\;\ast\;5\;+$ jest równy 23 (ponieważ $9 * 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 * 9 + 5$ .

Przykład 1

Oblicz wartość wyrażenia: $11 3 + 6 * 4 1 + -$ .

Porównaj swój sposób obliczeń z przedstawionym poniżej.

Pokaż rozwiązanie

Jako pierwszy rozważany operand weźmy liczbę 11.
Następnym operandem będzie liczba 3.
Dodajmy liczby 3 oraz 11.
Zapiszmy wynik sumy w miejscu operandów oraz znaku wykonanego obliczenia: $14\;6\;\ast\;4\;1\;+\;-$ .
Jako pierwszy operand weźmy liczbę 14.
Jako drugi operand weźmy liczbę 6.
Pomnóżmy przez siebie liczby 6 i 14.
Wynik mnożenia zapiszmy w miejscu operandów oraz znaku wykonanego obliczenia. Otrzymujemy: $84\;4\;1\;+\;-$ .
Jako pierwszy operand weźmy liczbę 84.
Jako drugi operand weźmy liczbę 4.
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.
Dodajmy do siebie liczby 4 i 1.
Sumę tych liczb zapiszmy w miejscu operandów oraz znaku wykonanego obliczenia: $84\;5\;–$ .
Jako jeden operand weźmy liczbę 84.
Jako drugi operand weźmy liczbę 5.
Odejmijmy od 84 liczbę 5.
Wynik działania $11\;3\;+\;6\;\ast\;4\;1\;+\;-$ jest równy 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 stosie. 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 * +.

Słownik

operand

liczba, na której wykonywane jest działanie

stos

struktura danych, w której informacje są pobierane ze szczytu i na niego odkładane; struktura typu LIFO (ang. Last In, First Out – ostatni na wejściu, pierwszy na wyjściu)

zapis infiksowy

zapis, w którym znak wykonywanego działania jest pomiędzy jego operandami

zapis postfiksowy

zapis, w którym znak wykonywanego działania jest zapisany po jego operandach

zapis prefiksowy

zapis, w którym znak wykonywanego działania jest zapisany przed jego operandami

Na dobry początek

Misja pierwsza: Ćwicz i zwyciężaj

ONP – wykonanie przykładowego działania

Algorytm obliczania wartości wyrażenia w ONP

Pseudokod obliczania wartości wyrażenia w ONP

Słownik