Odwrotna notacja polska

Przykład prostego mnożenia na kalkulatorze HP z wykorzystaniem ONP.

Odwrotna notacja polska (ONP, ang. reverse Polish notation, RPN, notacja postfiksowa, notacja przyrostkowa) – sposób zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach, 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ń^[1].

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^[1]^[2].

Odwrotna notacja polska została opracowana przez australijskiego naukowca Charlesa Hamblina(inne języki) jako „odwrócenie” beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych^[3]. Hamblin sugerował, aby notację tę nazwać „Azciweisakul notation” (Notacja Azciweisakuł – „Łukasiewicza” pisane od tyłu)^[4]^[5].

Przykłady

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 ma postać:

  2 7 + 3 / 14 3 − 4 × + 2 /

Zastosowanie

Odwrotna notacja polska jest powszechnie stosowana w kompilatorach wysokopoziomowych języków programowania, gdyż znacznie uprasza wykonywanie obliczeń^[6]. W początkowej fazie kompilacji wyrażenia matematyczne są konwertowane na ONP lub podobne zapisy, a następnie obliczane podczas wykonywania programu^[5]. Na przykład w Javie fragment:

public int add(int a, int b) {
    return a + b;
}

zostanie przekonwertowany na^[7]:

public int add(int, int);
    Code:
       0: iload_1
       1: iload_2
       2: iadd
       3: ireturn

W niektórych językach programowania ONP jest używana jako sposób zapisu wyrażeń matematycznych w kodzie pisanym przez programistę. Są to m.in. Forth, Postscript, Factor(inne języki), STOIC, Joy^[8]^[9]^[5].

W części kalkulatorów naukowych użytkownik wprowadza wyrażenia zgodnie z ONP. Takie kalkulatory produkują m.in. Hewlett-Packard, National Semiconductor oraz Casio. Niektóre kalkulatory umożliwiają przełączanie się między zapisem postfiksowym a infiksowym^[8]^[10].

ONP jest także wykorzystywana przez arkusze kalkulacyjne^[11].

ONP może być stosowana nie tylko do zapisu wyrażeń arytmetycznych, ale także logicznych np. wyrażenie $(A\lor B)\land C$ można zapisać w ONP jako $AB\lor C\land$ ^[5].

Obliczanie wartości wyrażenia w ONP

Algorytm^[8]

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. a₁...a_n)
  - odłóż na stos wynik funkcji dla parametrów a₁...a_n
Zdejmij ze stosu wynik.

Przykład 1

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

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

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ściowy oraz wyjściowy. Potrzebny jest także stos, przechowujący operatory niedodane jeszcze do ciągu wyjściowego. Program czyta kolejno wszystkie znaki wejścia i wykonuje odpowiednie operacje, zwracając uwagę na to, jaki typ symbolu jest wczytywany. W algorytmie są stosowane takie pojęcia jak priorytet i łączność operatorów, które należy rozumieć zgodnie z poniższą tabelą. Potęgowanie jest łączne prawostronnie, ponieważ w przypadku ciągu potęg (np. $3^{3^{3}}$ ) działania należy wykonywać od prawej strony. Dodawanie i mnożenie są obustronnie łączne, lecz tradycyjnie oblicza się je od lewej strony^[1]^[12].

Operator	Priorytet	Łączność
+ -	1	lewostronna
× /	2	lewostronna
^	3	prawostronna

Szczegóły algorytmu^[1]^[12]

Dopóki zostały symbole w łańcuchu wejściowym, wykonuj:

Przeczytaj pierwszy symbol od lewej.

Jeśli symbol jest liczbą, dodaj go do łańcucha wyjściowego.
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 nawiasem otwierającym, zdejmij element ze stosu i dodaj go do kolejki wyjście. Jeśli nawias otwierający nie został napotkany oznacza to, że oryginalny zapis był niepoprawny.

Jeśli symbol jest operatorem, o₁, wtedy:

1) dopóki na górze stosu znajduje się operator, o₂ taki, że:

o₁ jest lewostronnie łączny i jego priorytet wykonywania jest mniejszy lub równy priorytetowi wyk. o₂,

lub

o₁ jest prawostronnie łączny i jego priorytet wykonywania jest mniejsza od o₂,

zdejmij o₂ ze stosu i dołóż go do kolejki wyjściowej i wykonaj jeszcze raz 1)

2) włóż o₁ na stos operatorów.

Jeżeli symbol jest nawiasem otwierającym to odłóż go na stos.
Jeżeli symbol jest nawiasem zamykającym to zdejmuj operatory ze stosu i dokładaj je do łańcucha wyjściowego, dopóki symbol na górze stosu nie jest nawiasem otwierającym, kiedy dojdziesz do tego miejsca zdejmij nawias otwierający ze stosu bez dokładania go do łańcucha wyjściowego. Teraz, jeśli najwyższy element na stosie jest funkcją, także dołóż go do łańcucha wyjściowego. Jeśli stos zostanie opróżniony i nie napotkasz nawiasu otwierającego, oznacza to, że oryginalny zapis był niepoprawny.

Jeśli nie ma więcej symboli w łańcuchu wejściowym, zdejmuj wszystkie symbole ze stosu (jeśli jakieś są) i dodawaj je do łańcucha wyjściowego. (Powinny to być wyłącznie operatory, jeśli natrafisz na jakiś nawias oznacza to, że oryginalny zapis był niepoprawny.)

Przykład

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 ^ / +

Przypisy

1 2 3 4 Przeczytaj - Odwrotna notacja polska - zpe.gov.pl [online], zpe.gov.pl [dostęp 2026-06-04] .
↑ InayatI. Ali InayatI., Reverse Polish Notation (RPN) With Stack [online], Medium, 12 listopada 2019 [dostęp 2026-06-04] (ang.).
↑ UNSW Media Office, 10 Innovations that changed out world [online] [dostęp 2026-06-04] .
↑ Wprowadzenie - Obliczanie wartości wyrażeń w odwrotnej notacji polskiej - zpe.gov.pl [online], zpe.gov.pl [dostęp 2026-06-04] .
1 2 3 4 SławomirS. Gryś SławomirS., WaldemarW. Minkina WaldemarW., O znaczeniu odwrotnej notacji polskiej dla rozwoju technik informatycznych [online], 26 czerwca 2020 [dostęp 2026-06-04] (pol.).
↑ ONP - Odwrotna Notacja Polska [online], eduinf.waw.pl [dostęp 2026-06-04] .
↑ A.N.M. BazlurA.N.M.B. Rahman A.N.M. BazlurA.N.M.B., Java Bytecode Simplified: Journey to the Wonderland (Part 1) | Foojay.io [online], foojay, 8 marca 2022 [dostęp 2026-06-04] (ang.).
1 2 3 MarekM. Matejko MarekM., KrzysztofK. Mazur KrzysztofK., DawidD. Paszkot DawidD., Odwrotna notacja polska [online], 26 stycznia 2022 [dostęp 2026-06-04] (pol.).
↑ Factor tutorial by andreaferretti [online], andreaferretti.github.io [dostęp 2026-06-04] .
↑ National Semiconductor NS 4520 Handheld Electronic Calculator, the Scientist | Smithsonian Institution [online], www.si.edu [dostęp 2026-06-04] (ang.).
↑ 09, [MS-XLSB]: Formulas [online], learn.microsoft.com [dostęp 2026-06-04] (ang.).
1 2 RafałR. Hiszpański RafałR., Prosty parser. Część I: Odwrotna notacja polska [online], Rafał Hiszpański, 10 marca 2023 [dostęp 2026-06-04] .

[:0-1] 1 2 3 4 Przeczytaj - Odwrotna notacja polska - zpe.gov.pl [online], zpe.gov.pl [dostęp 2026-06-04] .

[2] InayatI. Ali InayatI., Reverse Polish Notation (RPN) With Stack [online], Medium, 12 listopada 2019 [dostęp 2026-06-04] (ang.).

[3] UNSW Media Office, 10 Innovations that changed out world [online] [dostęp 2026-06-04] .

[4] Wprowadzenie - Obliczanie wartości wyrażeń w odwrotnej notacji polskiej - zpe.gov.pl [online], zpe.gov.pl [dostęp 2026-06-04] .

[:2-5] 1 2 3 4 SławomirS. Gryś SławomirS., WaldemarW. Minkina WaldemarW., O znaczeniu odwrotnej notacji polskiej dla rozwoju technik informatycznych [online], 26 czerwca 2020 [dostęp 2026-06-04] (pol.).

[6] ONP - Odwrotna Notacja Polska [online], eduinf.waw.pl [dostęp 2026-06-04] .

[7] A.N.M. BazlurA.N.M.B. Rahman A.N.M. BazlurA.N.M.B., Java Bytecode Simplified: Journey to the Wonderland (Part 1) | Foojay.io [online], foojay, 8 marca 2022 [dostęp 2026-06-04] (ang.).

[:1-8] 1 2 3 MarekM. Matejko MarekM., KrzysztofK. Mazur KrzysztofK., DawidD. Paszkot DawidD., Odwrotna notacja polska [online], 26 stycznia 2022 [dostęp 2026-06-04] (pol.).

[9] Factor tutorial by andreaferretti [online], andreaferretti.github.io [dostęp 2026-06-04] .

[10] National Semiconductor NS 4520 Handheld Electronic Calculator, the Scientist | Smithsonian Institution [online], www.si.edu [dostęp 2026-06-04] (ang.).

[11] 09, [MS-XLSB]: Formulas [online], learn.microsoft.com [dostęp 2026-06-04] (ang.).

[:3-12] 1 2 RafałR. Hiszpański RafałR., Prosty parser. Część I: Odwrotna notacja polska [online], Rafał Hiszpański, 10 marca 2023 [dostęp 2026-06-04] .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]