Odwrotna notacja Polska (ONP) (ang. RPN – Reverse Polish Notation) - zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów.
Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.
W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:
2 + 2 6 - 4
3 * 5 12 / 3
Operatory posiadają priorytety, czyli "ważność". Jeśli w
wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną
wykonane te ważniejsze:
3 + 5 * 2 = 3 + 10 = 13
Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać
nawiasów:
(3 + 5) * 2 = 8 * 2 = 16
W ONP problem ten nie występuje. Operator zawsze występuje po
swoich argumentach:
2 2 + 6 4 -
3 5 * 12 3 /
Dzięki tej prostej zasadzie nawiasy stają się zbędne:
3 + 5 * 2 → 3 5 2 * + = 3 10 + =
13
(3 + 5) * 2 → 3 5 + 2 * = 8 2 * =
16
Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy
stosu. Zasada jest następująca:
Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli
napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to
ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne
z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy
wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie
znajdował się jego wynik.
- + - dodawanie
- - - odejmowanie
- * - mnożenie
- / - dzielenie
3. Przykład.
Brak komentarzy:
Prześlij komentarz