Podstawy programowania
wykład 13
Dr inż. Jakub Bauman
[e-mail]
Odwrotna notacja polska
Dr inż. Jakub Bauman
[e-mail]
Odwrotna notacja polska
Odwrotna notacja polska (ONP, ang. Reverse Polish
Notation, RPN)  jest sposobem zapisu wyrażeń
arytmetycznych, w którym znak wykonywanej operacji
umieszczony jest po operandach (zapis postfiksowy), a nie
pomiędzy nimi jak w konwencjonalnym zapisie
algebraicznym (zapis infiksowy) lub przed operandami jak w
zwykłej notacji polskiej (zapis prefiksowy). Zapis ten
pozwala na całkowitą rezygnację z użycia nawiasów w
wyrażeniach, jako że jednoznacznie określa kolejność
wykonywanych działań.
Zalety ONP
ONP bardzo ułatwia wykonywanie na komputerze obliczeń
z nawiasami i zachowaniem kolejności działań. Zarówno
algorytm konwersji notacji konwencjonalnej (infiksowej) na
odwrotnÄ… notacjÄ™ polskÄ… (postfiksowÄ…), jak i algorytm
obliczania wartości wyrażenia danego w ONP są bardzo
proste i wykorzystujÄ… stos.
Historia ONP
Odwrotna notacja polska została opracowana przez
australijskiego naukowca Charlesa Hamblina jako
 odwrócenie beznawiasowej notacji polskiej Jana
A
ukasiewicza na potrzeby zastosowań informatycznych.
Zastosowania ONP
Jest używana w niektórych językach programowania (np.
FORTH, Postscript) oraz w niektórych kalkulatorach
naukowych (np. Hewlett-Packard, National Semiconductor).
Programy komputerowe kompilujÄ…ce program dokonujÄ…
analizy wyrażenia arytmetycznego, przekształcając je na ciąg
instrukcji odpowiadajÄ…cy odwrotnej notacji polskiej.
Wyrażenie to jest obliczane podczas wykonywania programu.
Przykłady wyrażeń w ONP
*ð a+b a" a b +
*ð (a+b)*d a" a b+d *
*ð (a+(b*c)a" abc*+
*ð (a+b)*(c+d)a" a b +c d +*
*ð ((a+b)*((c+(d+e))(e+ f ))))a" a b +c d e++ e f + ^*
Algorytm konwersji na ONP
*ð 1. Analizuj wyrażenie po jednym elemencie (staÅ‚ej, zmiennej lub ograniczniku).
*ð 2. JeÅ›li ten element jest:
*ð a) staÅ‚Ä… lub nazwÄ… zmiennej  przekaż go na wyjÅ›cie;
*ð b) operatorem:
*ð - jeÅ›li priorytet badanego operatora jest wyższy od priorytetu operatora zajmujÄ…cego szczyt stosu lub jeÅ›li stos
jest pusty  dopisz go na stos;
*ð - jeÅ›li na szczycie stosu znajduje siÄ™ operator o wyższym lub równym priorytecie  odczytaj ze stosu i przeÅ›lij na
wyjście wszystkie operatory o priorytecie wyższym bądz
równym aż do wystąpienia na szczycie stosu operatora o
priorytecie niższym od priorytetu operatora nadchodzącego z wejścia; element badany dopisz na stos;
*ð c) nawiasem:
*ð - jeÅ›li trafiÅ‚eÅ› na nawias otwierajÄ…cy  dopisz go na stos;
*ð - jeÅ›li trafiÅ‚eÅ› na nawias zamykajÄ…cy: zdejmij wszystkie operatory ze stosu i przekaż je na wyjÅ›cie aż do trafienia na
nawias otwierający; nawiasów nie wypisuj na wyjście.
*ð 3. JeÅ›li badane wyrażenie
*ð a) nie zostaÅ‚o wyczerpane  wróć do punktu pierwszego;
*ð b) zostaÅ‚o wyczerpane  odczytaj wszystkie operatory ze stosu i przekaż je na wyjÅ›cie
automatu.
Priorytety operatorów
operator priorytet
funkcja
5
lg,sin, exp
potęgowanie 4
* ÷ ~ 3
+ - 2
= (przypisanie) 1
( 0
Przykład zamiany na ONP
Wyrażenie arytmetyczne: x + 3 * z  2 * 3 / k
Krok Wejście Stos Wyjście
1 x x
2 + +
3 3 + 3
4 * + *
5 z + * z
6   * +
7 2  2
8 *  *
9 3  * 3
10 /  / *
11 k  / k
12 koniec / 
Wyrażenie w notacji ONP: x 3 z * + 2 3 * k / 
Do czego to potrzebne?
Na przykład po to, żeby móc na swoje potrzeby
stworzyć bardziej zaawansowany kalkulator. Trudno
by nam było obliczyć zadanie zapisane nie w RPN.
Musielibyśmy szukać, które zadania mają wyższy
priorytet i je najpierw przeliczać (trzeba by najpierw
obliczyć wszystko w nawiasach).
Natomiast zadania zapisane w ONP w takim
przypadku Å‚atwiej siÄ™ oblicza.
Obliczanie wyrażenia zapisanego
w ONP
1. Analizuj wyrażenie po jednym elemencie (stałej, zmiennej lub
ograniczniku).
2. Jeśli ten element jest:
a) stałą lub nazwą zmiennej  dopisz go na stos;
b) operatorem  zdejmij ze stosu właściwą dla danego operatora
ilość argumentów, wykonaj na nich obliczenia, uzyskany wynik
dopisz na stos;
3. Jeśli badane wyrażenie
a) nie zostało wyczerpane  wróć do punktu pierwszego;
b) zostało wyczerpane  wartość znajdująca się na stosie to wynik
obliczeń.
Przykład
Wyrażenie: 6 3 / 2 5 + *
Krok Wejście Operacja Stos
1 6 6
2 3 6 3
3 / 6 / 3 2
4 2 2 2
5 5 2 2 5
6 + 2 + 5 2 7
7 * 2 * 7 14
Wartość wyrażenia: 14
Zadania do rozwiÄ…zania
*ð ZamieÅ„ nastÄ™pujÄ…ce wyrażenia na notacjÄ™ ONP, a
następnie oblicz wartość wyrażenia:
*ð (10+2)*5+(3-1)/2
*ð 7*(10-(1 +4)*2)-1
*ð 8+3+1-4*(12 +2*2)/2
*ð (9*9-1)/10-2*3
*ð 4-5+6*2-8*(1+3)
Pytania
Dyskusja
Dziękuję za uwagę!
Dr inż. Jakub Bauman
[e-mail]