Definicja:
Odwrotna notacja polska -
ONP, notacja polska (
reverse Polish notation), system notacji beznawiasowej umożliwiający zapisywanie wyrażeń w ten sposób, że argumenty operacji poprzedzają operatory (
notacja przyrostkowa).
Notacja ta, wprowadzona do logiki przez Jana Łukasiewicza, okazała się niezwykle przydatna do realizacji translatorów, które budują na stosie reprezentację tłumaczonych wyrażeń w ONP.
Przykład:
Wyrażenie (a+b) /c*(d- e) przełożone na ONP przyjmuje postać: ab+c/de-*.
Generując kod przekładu lub interpretując tak przełożone wyrażenie, translator ma uproszczone zadanie: zdejmuje kolejne elementy ze stosu i po napotkaniu operatora wykonuje działanie na dopiero co pobranych argumentach, kładąc wynik działania z powrotem na stos.
Hasło opracowano na podstawie “Słownika Encyklopedycznego – Informatyka”
Wydawnictwa Europa. Autor – Zdzisław Płoski.
ISBN 83-87977-16-0. Rok wydania 1999.
Inaczej:
Notacja infiksowa to notacja, którą posługujemy się na co dzień. Składa się ona z dwóch operand (
liczb, zmiennych) oraz operatora, który znajduje się między nimi np: 2+4 albo x*7 itd. W tak zapisanym wyrażeniu ważny jest priorytet operatora a nie jego kolejność. Oto priorytety w notacji infiksowej:
- Nawias,
- Dodawanie i odejmowanie,
- Mnożenie i dzielenie.
W Odwrotnej Notacji Polskiej jest inaczej. Nie jest ważny priorytet operatora, a jego
kolejność. Jest to bardzo przydatne w realizacji translatorów, które zdejmują kolejne operatory ze stosu, wykonują operacje i wynik odkładają na stosie. 2+4 w ONP wygląda następująco:
+2 4. Widać, że operator poprzedza operandy.
Uwaga! Zrozumienie algorytmu wymaga zapoznania się ze strukturą stosu.
Sposób zamiany wyrażenia zapisanego w notacji infiksowej na ONP
Czytamy wyrażenie od lewej strony i jeżeli natrafimy w nim na:
- liczbę lub zmienną – wypisujemy ją na wyjściu,
- nawias otwierający – kładziemy go na stosie,
- operator – zdejmujemy ze stosu i wypisujemy na wyjściu wszystkie operatory priorytecie niemniejszym niż ten wczytany. Następnie kładziemy wczytany operator na stosie,
- nawias zamykający – zdejmujemy ze stosu i wypisujemy na wyjściu wszystkie działania aż do napotkania nawiasu otwierającego, którego nie wypisujemy.