Odwrotna notacja polska (ONP, ang. reverse Polish notation, RPN) – sposób 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ń.
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.
Odwrotna notacja polska została opracowana przez australijskiego naukowca Charlesa Hamblina jako „odwrócenie” beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Hamblin sugerował, aby notację tę nazwać "Azciweisakul notation" (Notacja Azciweisakuł – „Łukasiewicza” pisane od tyłu).
Jest używana w niektórych językach programowania (np. FORTH, Postscript) oraz w niektórych kalkulatorach naukowych (np. Hewlett-Packard czy 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
[edytuj | edytuj kod]Wyrażenie, którego zapis w notacji infiksowej to
(2+3)×5
można zapisać w ONP następująco:
2 3 + 5 ×
Natomiast wyrażenie
((2+7)/3+(14−3)×4)/2
zapisane w ONP to
2 7 + 3 / 14 3 − 4 × + 2 /
Obliczanie wartości wyrażenia w ONP
[edytuj | edytuj kod]Algorytm
[edytuj | edytuj kod]- Dla wszystkich symboli z wyrażenia ONP wykonuj:
- jeśli i-ty symbol jest liczbą, to odłóż go na stos,
- jeśli i-ty symbol jest operatorem to:
- zdejmij ze stosu jeden element (ozn. a),
- zdejmij ze stosu kolejny element (ozn. b),
- odłóż na stos wartość b operator a.
- jeśli i-ty symbol jest funkcją to:
- zdejmij ze stosu oczekiwaną liczbę parametrów funkcji(ozn. a1...an)
- odłóż na stos wynik funkcji dla parametrów a1...an
- Zdejmij ze stosu wynik.
Przykład 1
[edytuj | edytuj kod]- Wyrażenie w notacji infiksowej: 12+2×(3×4+10/5)
- Wyrażenie ONP: 12 2 3 4 × 10 5 / + × +
- Gdy wczytany element jest liczbą, to zapisuje się ją na stos. W przeciwnym wypadku należy wykonać działanie arytmetyczne na 2 ostatnich liczbach na stosie. Wartość wyrażenia znajduje się na stosie.
Krok Wejście Stos Operacja 1 12 12 Odłóż na stos 2 2 12 2 Odłóż na stos 3 3 12 2 3 Odłóż na stos 4 4 12 2 3 4 Odłóż na stos 5 × 12 2 12 Zdejmij ze stosu dwa razy ( 3 i 4 ), następnie oblicz ( 3 × 4 = 12 ) a wynik odłóż na stos 6 10 12 2 12 10 Odłóż na stos 7 5 12 2 12 10 5 Odłóż na stos 8 / 12 2 12 2 Zdejmij ze stosu dwa razy ( 10 i 5 ), następnie oblicz ( 10 / 5 = 2 ) a wynik odłóż na stos 9 + 12 2 14 Zdejmij ze stosu dwa razy ( 12 i 2 ), następnie oblicz ( 12 + 2 = 14 ) a wynik odłóż na stos 10 × 12 28 Zdejmij ze stosu dwa razy ( 14 i 2 ), następnie oblicz ( 2 × 14 = 28 ) a wynik odłóż na stos 11 + 40 Zdejmij ze stosu dwa razy ( 28 i 12 ), następnie oblicz ( 12 + 28 = 40 ) a wynik odłóż na stos
- Wartość wyrażenia (zdejmij ze stosu ostatni element): 40
Przykład 2
[edytuj | edytuj kod]- Wyrażenie w notacji infiksowej: 5 + (1+2) × 4 − 3
- Wyrażenie ONP: 5 1 2 + 4 × + 3 −
Krok | Wejście | Stos | Operacja |
---|---|---|---|
1 | 5 | 5 | Odłóż na stos |
2 | 1 | 5 1 | Odłóż na stos |
3 | 2 | 5 1 2 | Odłóż na stos |
4 | + | 5 3 | Zdejmij ze stosu dwa razy ( 1 i 2 ), następnie oblicz ( 1 + 2 = 3 ) a wynik odłóż na stos |
5 | 4 | 5 3 4 | Odłóż na stos |
6 | × | 5 12 | Zdejmij ze stosu dwa razy ( 3 i 4 ), następnie oblicz ( 3 × 4 = 12 ) a wynik odłóż na stos |
7 | + | 17 | Zdejmij ze stosu dwa razy ( 5 i 12 ), następnie oblicz ( 5 + 12 = 17 ) a wynik odłóż na stos |
8 | 3 | 17 3 | Odłóż na stos |
9 | − | 14 | Zdejmij ze stosu dwa razy ( 17 i 3 ), następnie oblicz ( 17 − 3 = 14 ) a wynik odłóż na stos |
- Wartość wyrażenia (zdejmij ze stosu ostatni element): 14
Konwersja z notacji infiksowej do ONP
[edytuj | edytuj kod]Edsger Dijkstra jest autorem algorytmu nazywanego „stacją rozrządową”, ponieważ jest w działaniu bardzo podobny do kolejowej stacji rozrządowej. Tak jak algorytm liczący wartość wyrażenia ONP, działa na bazie stosu. Do konwersji używane są dwa łańcuchy znaków – wejście oraz wyjście. Potrzebny jest także stos, przechowujący operatory niedodane jeszcze do wyjścia. Program czyta kolejno wszystkie znaki wejścia i wykonuje odpowiednie operacje, zwracając uwagę na to, jaki typ znaku jest wczytywany.
Szczegóły algorytmu
[edytuj | edytuj kod]- Dopóki zostały symbole do przeczytania, wykonuj:
- Przeczytaj symbol.
- Jeśli symbol jest liczbą dodaj go do kolejki wyjście.
- Jeśli symbol jest funkcją włóż go na stos.
- Jeśli symbol jest znakiem oddzielającym argumenty funkcji (np. przecinek):
- Dopóki najwyższy element stosu nie jest lewym nawiasem, zdejmij element ze stosu i dodaj go do kolejki wyjście. Jeśli lewy nawias nie został napotkany oznacza to, że znaki oddzielające zostały postawione w złym miejscu lub nawiasy są źle umieszczone.
- Jeśli symbol jest operatorem, o1, wtedy:
- 1) dopóki na górze stosu znajduje się operator, o2 taki, że:
- o1 jest lewostronnie łączny i jego kolejność wykonywania jest mniejsza lub równa kolejności wyk. o2,
- lub
- o1 jest prawostronnie łączny i jego kolejność wykonywania jest mniejsza od o2,
- zdejmij o2 ze stosu i dołóż go do kolejki wyjściowej i wykonaj jeszcze raz 1)
- 2) włóż o1 na stos operatorów.
- Jeżeli symbol jest lewym nawiasem to włóż go na stos.
- Jeżeli symbol jest prawym nawiasem to zdejmuj operatory ze stosu i dokładaj je do kolejki wyjście, dopóki symbol na górze stosu nie jest lewym nawiasem, kiedy dojdziesz do tego miejsca zdejmij lewy nawias ze stosu bez dokładania go do kolejki wyjście. Teraz, jeśli najwyższy element na stosie jest funkcją, także dołóż go do kolejki wyjście. Jeśli stos zostanie opróżniony i nie napotkasz lewego nawiasu, oznacza to, że nawiasy zostały źle umieszczone.
- Przeczytaj symbol.
- Jeśli nie ma więcej symboli do przeczytania, zdejmuj wszystkie symbole ze stosu (jeśli jakieś są) i dodawaj je do kolejki wyjścia. (Powinny to być wyłącznie operatory, jeśli natrafisz na jakiś nawias oznacza to, że nawiasy zostały źle umieszczone.)
Przykład
[edytuj | edytuj kod]Wejście 3+4×2/(1−5)^2 Przeczytaj "3" Dodaj "3" do wyjścia Wyjście: 3
Przeczytaj "+" Włóż "+" na stos Wyjście: 3 Stos: +
Przeczytaj "4" Dodaj "4" do wyjścia Wyjście: 3 4 Stos: +
Przeczytaj "×" Włóż "×" na stos Wyjście: 3 4 Stos: + ×
Przeczytaj "2" Dodaj "2" do wyjścia Wyjście: 3 4 2 Stos: + ×
Przeczytaj "/" Zdejmij "×" ze stosu i dodaj do wyjścia, włóż "/" na stos Wyjście: 3 4 2 × Stos: + /
Przeczytaj "(" Włóż "(" na stos Wyjście: 3 4 2 × Stos: + / (
Przeczytaj "1" Dodaj "1" do wyjścia Wyjście: 3 4 2 × 1 Stos: + / (
Przeczytaj "−" Włóż "−" na stos Wyjście: 3 4 2 × 1 Stos: + / ( −
Przeczytaj "5" Dodaj "5" do wyjścia Wyjście: 3 4 2 × 1 5 Stos: + / ( −
Przeczytaj ")" Zdejmij "−" ze stosu i dodaj do wyjścia, zdejmij "(" ze stosu Wyjście: 3 4 2 × 1 5 − Stos: + /
Przeczytaj "^" Włóż "^" na stos Wyjście: 3 4 2 × 1 5 − Stos: + / ^
Przeczytaj "2" Dodaj "2" do wyjścia Wyjście: 3 4 2 × 1 5 − 2 Stos: + / ^
Koniec wyrażenia Zdejmij stos na wyjście Wyjście: 3 4 2 × 1 5 − 2 ^ / +
Zamiana wyrażenia algebraicznego zapisanego w notacji infiksowej na postać postfiksową (ONP)
[edytuj | edytuj kod]Operator | Priorytet |
---|---|
( | 0 |
+ − ) | 1 |
× / % | 2 |
^ | 3 |
Gdy wczytany element jest:
- stałą lub nazwą zmiennej, to przesyłamy go na wyjście.
- ( to dopisujemy go na stos.
- ) to odczytaj ze stosu i prześlij na wyjście wszystkie operatory aż do nawiasu (, który należy odczytać, ale nie wysyłać na wyjście.
- +, −, ×, /, %, ^. Dopóki na szczycie stosu znajduje się operator o priorytecie wyższym lub równym od priorytetu operatora wczytanego, ściągaj operatory ze stosu na wyjście; następnie połóż operator wczytany na stosie.
Na koniec, gdy wszystkie elementy zostały wczytane należy zdjąć wszystkie operatory ze stosu i przesłać je na wyjście.
- Przykład :
Wyrażenie: 12 + a × (b × c + d / e)
Krok | Wejście | Stos | Wyjście |
---|---|---|---|
1 | 12 | 12 | |
2 | + | + | |
3 | a | + | a |
4 | × | ×+ | |
5 | ( | (×+ | |
6 | b | (×+ | b |
7 | × | ×(×+ | |
8 | c | ×(×+ | c |
9 | + | +(×+ | × |
10 | d | +(×+ | d |
11 | / | /+(×+ | |
12 | e | /+(×+ | e |
13 | ) | /+(×+ | /+ |
14 | ×+ | ×+ | |
15 | koniec |
ONP: 12 a b c × d e / + × +