Odwrotna notacja polska, onp, notacja polska (reverse Polish notation), system notacji beznawiasowej umożliwiający zapisywanie



Pobieranie 10,26 Kb.
Data04.11.2017
Rozmiar10,26 Kb.

Odwrotna notacja polska, ONP, notacja polska (reverse Polish notation), jest to 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ć



a b + c / d e – *

Odwrotna notacja polska inaczej RPN (ang. Reverse Polish Notation) jest sposobem 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 ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.

Na przykład konwencjonalny zapis:

(2 + 3) * 5

w RPN wygląda tak:

2 3 + 5 *

natomiast:

((2 + 7 / 3) + (14 - 3) * 4) / 2

zapiszemy następująco:

3 / 2 + 14 3 - 4 * + 2 /
Stos jest prostą strukturą danych, która dostarcza dwie podstawowe operacje:


Stos jest też nazywany kolejką LIFO (ang. Last In First Out), ponieważ jako pierwszy zostanie odczytany element ostatnio odłożony na stos (nie możemy nic wyjąć ze środka stosu).

Algorytm obliczenia wartości wyrażenia RPN (wersja 1)


  1. wyzeruj stos

  2. dla wszystkich symboli z wyrażenia RPN wykonuj:

    1. jeśli i-ty symbol jest liczbą, to odłóż go na stos

    2. jeśli i-ty symbol jest operatorem to:

      1. zdejmij ze stosu jeden element (ozn. a)

      2. zdejmij ze stosu kolejny element (ozn. b)

      3. odłóż na stos wartość b operator a

  3. zdejmij ze stosu wynik

 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:

1) Nawias

2) Dodawanie i odejmowanie

3) 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.
Algorytm infiks 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



©operacji.org 2019
wyślij wiadomość

    Strona główna