Loading AI tools
sposób zapisu wyrażeń arytmetycznych Z Wikipedii, wolnej encyklopedii
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.
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 /
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 |
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 |
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.
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 ^ / +
Operator | Priorytet |
---|---|
( | 0 |
+ − ) | 1 |
× / % | 2 |
^ | 3 |
Gdy wczytany element jest:
Na koniec, gdy wszystkie elementy zostały wczytane należy zdjąć wszystkie operatory ze stosu i przesłać je na wyjście.
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 / + × +
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.