Odwrotna notacja polska (ang. Reverse Polish Notation, RPN) – 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), 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ń.
RPN 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 została opracowana przez australijskiego naukowca Charlesa Hamblina jako "odwrócenie" bez nawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Hamblin sugerował aby notację tą nazwać "Azciweisakul notation" (Notacja Azciweisakuł – "Łukasiewicza" pisane od tyłu).
Jest używana w niektórych językach programowania (np. FORTH, Postscript) oraz w niektórych kalkulatorach naukowych (np. Hewlett-Packard, National Semiconductor). Programy komputerowe kompilujące program dokonują analizy wyrażenia arytmetycznego, przekształcając je na ciąg instrukcji odpowiadający odwrotnej notacji polskiej. Wyrażenie to jest obliczane podczas wykonywania programu.[1]
Przykłady:
notacja infiksowa: ONP, notacja postfiksowa:
(2+3)*5 -> 2 3 + 5 *
((2+7)/3+(14-3)*4)/2 -> 2 7 + 3 / 14 3 - 4 * + 2 /
Algorytm zamiany z notacji infiksowej na postfiksową:
Algorytm stacji rozrządowej Dijkstry:
Algorytm ten służy do konwersji wyrażenia z postaci infiksowej do ONP. Nazwa zapewne nawiązuje do funkcjonowania jakiegoś domowego systemu kolei wąskotorowej typu zrób-to-sam:P Do przygotowania algorytmu musimy zaopatrzyć się w stos i kolejkę wyjścia. Działanie algorytmu prześledźmy na poniższym przykładzie. Na starcie mamy:
wejście: 4*3-6/(1+2)
stos: NULL
wyjście: NULL
Pobieramy pierwszy symbol 4. Jest to liczba - algorytm mówi, że należy ją przesunąć do wyjścia. Następny symbol to *. Tym razem - jako że jest to operator - przesuwamy go na stos. Kolejny symbol (liczbę 3) podobnie jak 4 przesuwamy na wyjście. W tym momencie sytuacja wygląda tak:
wejście: -6/(1+2)
stos: *
wyjście: 4 3
Pobieramy kolejny symbol. Jest to operator -, który wypadałby przenieść na stos. Niestety siedzi już tam *. Nie możemy dopuścić do sytuacji, w której na stosie znajduje się operator o niższym priorytecie niż ten pod nim. Musimy więc przenieść operator * na wyjście. Gdy nic nam już nie przeszkadza, możemy spokojnie umieścić - na stosie, a kolejny element - liczbę 6 na wyjściu. Mamy:
wejście: /(1+2)
stos: -
wyjście: 4 3 * 6
Jedziemy dalej. Następny w kolejce jest operator /, który powinniśmy umieścić na stosie. Możemy to zrobić, gdyż co prawda jest już tam inny operator (-), ale ma on niższy priorytet niż /. Kolejny symbol - nawias ( traktujemy tutaj jako operator o bardzo wysokim priorytecie (o tym czemu - za chwilę) i kładziemy na stosie. 1 jak zwykle jest to z liczbą - przesuwamy na wyjście.
wejście: +2)
stos: - / (
wyjście: 4 3 * 6 1
Teraz zaczyna się magia. Dochodzimy do +, który powinniśmy przełożyć na stos. Jak zawsze w tym wypadku sprawdzamy co już znajduje się na stosie i jaki ma priorytet. Powstaje więc pytanie jak traktować (? Otóż należy przyjąć, że nawias na stosie przykrywa wszystko co znajduje się pod nim, nie musimy się bać o priorytety operatorów. Nawiasem możemy przykryć dowolny operator. Możemy na nim również położyć dowolny operator. Tak też robimy z + i zajmujemy się też 2.
wejście: )
stos: - / ( +
wyjście: 4 3 * 6 1 2
Napotykając zamykający nawias ) na wejściu, należy ściągać poszczególne symbole ze stosu i przenosić je na wyjście aż napotkamy nawias otwierający (. Nawiasów nie odkładamy na wyjście, nie są one nam już potrzebne. Opróżniliśmy już potok wejścia, ale na stosie nadal są symbole - /. Należy je również ściągać jeden po drugim ze stosu i kierować na wyjście. Oto co otrzymujemy:
wejście: NULL
stos: NULL
wyjście: 4 3 * 6 1 2 + / -
Co dalej?
Mamy teraz kolejkę symboli 4 3 * 6 1 2 + / -. Jak należy zaimplementować operacje na tej kolejce aby obliczyć wartość wyrażenia ONP? Otóż najłatwiej skorzystać z kolejnego stosu. Pobieramy kolejno symbol za symbolem i odkładamy go na stos. Robimy tak dopóki nie natrafimy na jakiś operator. Wtedy należy ściągnąć dwa elementy ze stosu i wykonać na nich działanie określone przez operator. Proste.
Oto jak wyglądałoby obliczanie powyższego wyrażenia krok po kroku (przypominam, że ze stosu zdejmujemy elementy z końca a z kolejki - z początku):
stos: NULL, kolejka: 4 3 * 6 1 2 + / -
stos: 4 3, kolejka: * 6 1 2 + / -
stos: 12, kolejka: 6 1 2 + / -
stos: 12 6 1 2, kolejka: + / -
stos: 12 6 3, kolejka: / -
stos: 12 2, kolejka: -
stos: 10, kolejka: NULL
Ostatni element na stosie to wynik. Jeżeli zostanie nam więcej niż jeden element, to znaczy, że gdzieś popełniliśmy błąd. [2]
Źródła:
[1] http://pl.wikipedia.org/wiki/Odwrotna_notacja_polska
[2] http://www.dsv.agh.edu.pl/~lfx/programowanie/onp
RPN 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 została opracowana przez australijskiego naukowca Charlesa Hamblina jako "odwrócenie" bez nawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Hamblin sugerował aby notację tą nazwać "Azciweisakul notation" (Notacja Azciweisakuł – "Łukasiewicza" pisane od tyłu).
Jest używana w niektórych językach programowania (np. FORTH, Postscript) oraz w niektórych kalkulatorach naukowych (np. Hewlett-Packard, National Semiconductor). Programy komputerowe kompilujące program dokonują analizy wyrażenia arytmetycznego, przekształcając je na ciąg instrukcji odpowiadający odwrotnej notacji polskiej. Wyrażenie to jest obliczane podczas wykonywania programu.[1]
Przykłady:
notacja infiksowa: ONP, notacja postfiksowa:
(2+3)*5 -> 2 3 + 5 *
((2+7)/3+(14-3)*4)/2 -> 2 7 + 3 / 14 3 - 4 * + 2 /
Algorytm zamiany z notacji infiksowej na postfiksową:
Algorytm stacji rozrządowej Dijkstry:
Algorytm ten służy do konwersji wyrażenia z postaci infiksowej do ONP. Nazwa zapewne nawiązuje do funkcjonowania jakiegoś domowego systemu kolei wąskotorowej typu zrób-to-sam:P Do przygotowania algorytmu musimy zaopatrzyć się w stos i kolejkę wyjścia. Działanie algorytmu prześledźmy na poniższym przykładzie. Na starcie mamy:
wejście: 4*3-6/(1+2)
stos: NULL
wyjście: NULL
Pobieramy pierwszy symbol 4. Jest to liczba - algorytm mówi, że należy ją przesunąć do wyjścia. Następny symbol to *. Tym razem - jako że jest to operator - przesuwamy go na stos. Kolejny symbol (liczbę 3) podobnie jak 4 przesuwamy na wyjście. W tym momencie sytuacja wygląda tak:
wejście: -6/(1+2)
stos: *
wyjście: 4 3
Pobieramy kolejny symbol. Jest to operator -, który wypadałby przenieść na stos. Niestety siedzi już tam *. Nie możemy dopuścić do sytuacji, w której na stosie znajduje się operator o niższym priorytecie niż ten pod nim. Musimy więc przenieść operator * na wyjście. Gdy nic nam już nie przeszkadza, możemy spokojnie umieścić - na stosie, a kolejny element - liczbę 6 na wyjściu. Mamy:
wejście: /(1+2)
stos: -
wyjście: 4 3 * 6
Jedziemy dalej. Następny w kolejce jest operator /, który powinniśmy umieścić na stosie. Możemy to zrobić, gdyż co prawda jest już tam inny operator (-), ale ma on niższy priorytet niż /. Kolejny symbol - nawias ( traktujemy tutaj jako operator o bardzo wysokim priorytecie (o tym czemu - za chwilę) i kładziemy na stosie. 1 jak zwykle jest to z liczbą - przesuwamy na wyjście.
wejście: +2)
stos: - / (
wyjście: 4 3 * 6 1
Teraz zaczyna się magia. Dochodzimy do +, który powinniśmy przełożyć na stos. Jak zawsze w tym wypadku sprawdzamy co już znajduje się na stosie i jaki ma priorytet. Powstaje więc pytanie jak traktować (? Otóż należy przyjąć, że nawias na stosie przykrywa wszystko co znajduje się pod nim, nie musimy się bać o priorytety operatorów. Nawiasem możemy przykryć dowolny operator. Możemy na nim również położyć dowolny operator. Tak też robimy z + i zajmujemy się też 2.
wejście: )
stos: - / ( +
wyjście: 4 3 * 6 1 2
Napotykając zamykający nawias ) na wejściu, należy ściągać poszczególne symbole ze stosu i przenosić je na wyjście aż napotkamy nawias otwierający (. Nawiasów nie odkładamy na wyjście, nie są one nam już potrzebne. Opróżniliśmy już potok wejścia, ale na stosie nadal są symbole - /. Należy je również ściągać jeden po drugim ze stosu i kierować na wyjście. Oto co otrzymujemy:
wejście: NULL
stos: NULL
wyjście: 4 3 * 6 1 2 + / -
Co dalej?
Mamy teraz kolejkę symboli 4 3 * 6 1 2 + / -. Jak należy zaimplementować operacje na tej kolejce aby obliczyć wartość wyrażenia ONP? Otóż najłatwiej skorzystać z kolejnego stosu. Pobieramy kolejno symbol za symbolem i odkładamy go na stos. Robimy tak dopóki nie natrafimy na jakiś operator. Wtedy należy ściągnąć dwa elementy ze stosu i wykonać na nich działanie określone przez operator. Proste.
Oto jak wyglądałoby obliczanie powyższego wyrażenia krok po kroku (przypominam, że ze stosu zdejmujemy elementy z końca a z kolejki - z początku):
stos: NULL, kolejka: 4 3 * 6 1 2 + / -
stos: 4 3, kolejka: * 6 1 2 + / -
stos: 12, kolejka: 6 1 2 + / -
stos: 12 6 1 2, kolejka: + / -
stos: 12 6 3, kolejka: / -
stos: 12 2, kolejka: -
stos: 10, kolejka: NULL
Ostatni element na stosie to wynik. Jeżeli zostanie nam więcej niż jeden element, to znaczy, że gdzieś popełniliśmy błąd. [2]
Źródła:
[1] http://pl.wikipedia.org/wiki/Odwrotna_notacja_polska
[2] http://www.dsv.agh.edu.pl/~lfx/programowanie/onp
Posty
Brak komentarzy:
Prześlij komentarz