Odwrotna notacja polska (ONP) (inaczej RPN, z ang. Reverse Polish Notation) 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). 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 RPN są bardzo proste i wykorzystują stos.
Odwrotna notacja polska powstała z beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Jest używana w niektórych językach programowania (FORTH, Postscript) oraz w kalkulatorach naukowych firmy Hewlett-Packard. Programy komputerowe dokonując analizy wyrażenia arytmetycznego często przekształcają je na odwrotną notację polską.
1. Opis notacji
W odwrotnej notacji polskiej działania zapisuje się w postaci ciągu wyrazów rozdzielonych spacjami. Pod nazwą wyraz rozumie się liczbę lub działanie.
1.1. Liczby
Liczbą jest ciąg cyfr zawierający co najwyżej jednej znak kropki, służący do oddzielania części całkowitej od części ułamkowej. Do oddzielania części całkowitej i ułamkowej nie stosuje się znaku przecinka. Liczba może być bezpośrednio poprzedzona znakiem minus w celu oznaczenia liczb mniejszych od zera. Liczba może być zakończona literą e (małą lub dużą) i występującą bezpośrednio za nią liczbą całkowitą dodatnią lub ujemną. Zapis zeX oznacza weź: liczbę z i przemnóż ją przez liczbę 10 podniesioną do potęgi X.
| Zapis w Odwrotnej Notacji Polskiej | Zapis tradycyjny |
|---|---|
zeX = z 10 X ^ * |
z × 10X |
z.yE-X = z.y 10 -X ^ * |
z.y × 10–X |
1.2. Działania
Działaniem jest ciąg znaków niecyfrowych informujących jaką operację matematyczną należy wykonać na zapamiętanych liczbach. Działania dzielimy na podstawowe (dwuliczbowe i jednoliczbowe) oraz potomne. Spis dostępnych działań znajduje się niżej.
2. Działania
W rozdziale tym literami a i b oznaczono dowolne liczby.
2.1. Działania podstawowe
2.1.1. Działania podstawowe dwuliczbowe
| Zapis w Odwrotnej Notacji Polskiej | Zapis tradycyjny |
|---|---|
a b + |
a + b |
a b - |
a – b |
a b * |
a × b |
a b / |
a / b |
a b ^ |
ab |
2.1.2. Działania podstawowe jednoliczbowe
W chwili obecnej nie ma zdefiniowanych jednoliczbowych działań podstawowych.
2.2. Działania potomne
Działania potomne definiuje się w celu przyspieszenia posługiwania się ONP i zastępują one często wykorzystywane działania podstawowe o szczególnej strukturze.
| Zapis w Odwrotnej Notacji Polskiej | Zapis tradycyjny |
|---|---|
1 a / |
1 / a |
a // |
1 / a |
a -1 ^ |
a–1 |
a ^^ |
a2 |
a 2 ^ |
a2 |
a ^^^ |
a3 |
a 3 ^ |
a3 |
Dygresja: Na upartego również działanie dzielenia a b / można by uznać za działanie potomne, bo dzielenie zapisać można jako złożenie potęgowania i mnożenia. Podobnie rzecz się ma z odejmowaniem a b -, które może być złożeniem mnożenia i dodawania.
| Zapis w Odwrotnej Notacji Polskiej | Równoważnik podstawowy |
|---|---|
a b / |
a b -1 ^ * |
a b - |
a b -1 * + |
3. Przykłady
| Zapis w Odwrotnej Notacji Polskiej | Zapis tradycyjny |
|---|---|
1 2 + 4 * 3 + |
[(1 + 2) * 4] + 3 |
3 4 2 * 1 5 - 2 ^ / + |
3 + 4*2/(1-5)2 |