Algorytmy

Odwrotna notacja polska

  • 2010-09-24 18:02
  • 9 komentarzy
  • 15945 odsłon
  • Oceń ten tekst jako pierwszy
WSTĘP

Odwrotna notacja polska, inaczej RPN (z ang. Reverse Polish Notation) to sposób zapisu wyrażeń arytmetycznych beznawiasowo. Czyli, np. mając wyrażenie (zapis infiksowy):

(2+1)*3-4*(7+4)


w RPN będzie wyglądać tak (zapis postfiksowy):

2 1 + 3 * 4 7 4 + * -


Po co to nam jest potrzebne? A choćby po to, żeby móc na swoje potrzeby stworzyć bardziej zaawansowany kalkulator. Trudno by nam było obliczyć zadanie zapisane nie w RPN. Musielibyśmy szukać, które zadania mają wyższy priorytet i je najpierw przeliczać (w nawiasach trzeba by było wszystko obliczyć, przez co trzeba się liczyć z tym, że należałoby skakać w ciągu zadania z jednego nawiasu do drugiego, później wracać itd., co na pewno można przypłacić pomyłką). Zadania zapisane w RPN w takim przypadku łatwiej się oblicza.

Jak obliczyć RPN?

Odwrotna notacja polska ułatwia nam zadanie i pozbawia wielu problemów, o których wspomniałem wcześniej. W tym przypadku nie trzeba przeskakiwać z jednego równania do drugiego w całym ciągu zadania. Wystarczy skanować ciąg arytmetyczny od strony lewej do prawej wykorzystując stos. Algorytm obliczania RPN wygląda tak:

1. Pobierz znak z ciągu i skocz w lewo.
2. Jeżeli jest to liczba to odłóż ją na stos, natomiast, jeżeli jest to jakiś znak arytmetyczny to pobierz tyle liczb ze stosu, aby można było obliczyć to równanie, np. dla dodawania, odejmowania, mnożenia i dzielenia są to dwie kolejne liczby, ale już dla negacji (NEG) wystarczy pobrać tylko jedną liczbę. I tutaj mała uwaga. Pobierając dwie liczby, np. 2 i 3, równanie wykonuje się w odwrotnej kolejności, czyli, np. 3 + 2.
Wynik działania arytmetycznego odkładamy ponownie na stos.
3. Jeżeli koniec równania to pobierz wynik ze stosu, który jest rozwiązaniem równania. Natomiast, jeżeli nie jest to koniec to wróć do punktu pierwszego.

W praktyce wygląda to tak (w kolejnych taktach):

równanie: 2 1 + 3 * 4 7 4 + * -

TaktWejścieStos*Wyjście
122,#
211,2,#
3+3,#2 + 1
433,3,#
5*9,#3 * 3
644,9,#
777,4,9,#
844,7,4,9,#
9+11,4,9,#7 + 4
10*44,9,#4 * 11
11--35,#9 - 44
12KONIEC#ze stosu wynik -35


  • Stos ? jest to bufor, który rządzi się zasadą LIFO (Last In First Out), czyli ostatni przyszedł, pierwszy wychodzi. Inaczej mówiąc co dodaliśmy do stosu jako ostatni element, to tylko ten element możemy pobrać jako pierwszy. W przykładzie wyżej hash (#) oznacza dno stosu.

Jak przekształcić równanie do RPN

Sposób przekształcenia do odwrotnej notacji polskiej też nie jest trudny. Wszystko odbywa się na takiej zasadzie, że czytając równanie od lewej do prawej, wyrażenia arytmetyczne odkładamy na stos a liczby na wyjście. Trzeba natomiast pamiętać o pewnych regułach. Bardzo ważną sprawą jest priorytet zadania, czyli jak wspomniałem mnożenie ma wyższy priorytet od dodawania. Dodatkowo, odkładając wyrażenie arytmetyczne możemy je odłożyć tylko wtedy, jeżeli ostatnim elementem stosu jest wyrażenie o niższym priorytecie. Jeżeli jest wyższe lub równe to zdejmuj dotąd elementy z niego i wysyłaj na wyjście aż ostatnie wyrażenie będzie niższe, bądź dojdziemy do dna stosu.
Z nawiasami sprawa wygląda trochę inaczej. Nie traktujemy ich w ogóle jako priorytet. Jeżeli dojdziemy do otwarcia nawiasu "(", to odkładamy go na stos (mimo jakiegokolwiek elementu na stosie, bądź jego brak). Odkładając nawias otwierający będziemy go traktować jakby on był dnem stosu.
Kiedy dojdziemy do nawiasu zamykającego ")", to nigdzie go nie odkładając (nawet na wyjście); dotąd zdejmujemy elementy ze stosu i wysyłamy na wyjście, aż dojdziemy do nawiasu otwierającego, którego również zdejmujemy ale już nie odkładamy na wyjście. A teraz przykład:

Mamy równanie:
(2+1)*3-4*(7+4)


Tabela z kolejnymi taktami:

TaktWejścieStosWyjście
1((,#
22(,#2
3++,(,#
41+,(,#1
5)#+
6**,#
73*,#3
8--,#*
94-,#4
10**,-,#
11((,*,-,#
127(,*,-,#7
13++,(,*,-,#
144+,(,*,-,#4
15)*,-,#+
16KONIEC-,#*
17#-


I teraz czytając Wyjście od góry mamy wynik:
2 1 + 3 * 4 7 4 + * -

Wynik jest taki, jak pokazałem wyżej.

Uwagi końcowe ? moje spostrzeżenia.

Poddając zadanie fazie przekształcenia równania na RPN, powinniśmy zrobić pewną weryfikacje zadania, czyli sprawdzić je pod względem prawidłowości. Na przykład ktoś może podać równanie:

7(2+1)


Jak widzimy, osoba nie postawiła znaku mnożenia przed nawiasem. To może spowodować błąd przy obliczeniach. Dlatego wyrażenie powyższe powinniśmy zamienić na 7*(2+1). Zadanie: (2+1)3 na (2+1)*3.

Następna sprawa to znak negacji (możemy przyjąć go w rozważaniach jako NEG). Na przykład równanie:

NEG 5 + 1

Oznacza to, że piątkę trzeba zanegować na ?5 i dalej obliczać. Trzeba pamiętać o tym, że negacja jest jednoargumentowa i przy obliczaniu RPN ze stosu pobieramy tylko jeden element, negujemy go i znowu odkładamy na stos. Negowanie (NEG) ma priorytet równy mnożeniu i dzieleniu.
Ale czy naprawdę potrzebne jest nam negacja? Okazuje się, że tak. Przykład:

-2+3


Powyższe zadanie nie uda nam się obliczyć po przekształceniu na RPN. Zamieniając przykład na zapis postfiksowy równanie będzie wyglądało:

2-3+


I teraz obliczając: 2 idzie na stos. Dalej znak minus, czyli zdejmujemy dwa znaki ze stosu i obliczamy. I tu jest problem, bo na stosie jest tylko jedna odłożona liczba! Tak samo problem wygląda w nawiasach:

3+(-2)


Powyższe równanie jest prawidłowe, ale będzie problem z obliczeniem.

Co w takim przypadku zrobić? Odpowiedź jest prosta, choć wydaje się dużym problemem. Znaki minus, które występują na samym początku równania jak i zaraz po nawiasie otwierającym trzeba zamienić na negacje. Czyli równanie: -3+2*(-4+7) należy zapisać jako NEG3+2*(NEG4+7). I sprawa rozwiązana a obliczanie negacji jest proste, co już opisałem wyżej.

9 komentarzy

eldamiani 2008-01-31 20:38

-3+2
można zapisać jako
(0-3)+2,
2*(-3) jest równoważne 2*(0-3),
także nie jest potrzebne wprowadzanie dodatkowej wartości NEG, ponieważ można zbadać czy przed minusem stoi jakaś liczba, czy też jest to jakiś znak matematyczny lub może początek wyrażenia. W każdym takim wykrytym przypadku można wstawić 0 przed liczbą z minusem i otoczyć to nawiasem.
-3*2 = -6    ==    (0-3)*2 = -6.
Myślę, że to może pomóc w niektórych sytuacjach. W moim programie było mi łatwiej zrobić własnie coś takiego.

Z góry przepraszam Misiekd, że poprawiłem swój komentarz w późnieszjym czasie.

Misiekd 2008-04-06 20:28

-3 * 2 = -6 ==  0 - 3 * 2 = -6
jak już to
-3 * 2 = -6 ==  (0 - 3) * 2 = -6
bo przy
-3 * -3 to co innego niż 0 - 3 * 0 - 3

George 2007-10-20 04:46

Bardzo dobry artykul. Dodam jeszcze, ze :

Algorytm nie zadziala w przypadku -1 * -1. NEG nalezy uzywac nie tylko wowczas kiedy jest na poczatku lub zaraz za nawiasem, a wowczas gdy flaga bNeg jest true. Flage bNeg nalezy ustawic w nastepujacych sytuacjach:
a) Przed petla
b) Po nawiasie (
b) Po dowolnym operatorze
A ustawic na false po liczbie i po nawiasie )
W ten sposob operacja 1 * --1 tez bedzie okay.

Coldpeer 2008-04-06 23:07

Jakby ktoś chciał kod konwersji notacji infix->postfix (czyli z normalnego na ONP) w Pythonie, to http://coldpeer.jogger.pl/2007[...]tna-notacja-polska-w-pythonie/

Twardy 2007-03-04 20:51

Wszystko jest opisane w artykule. Bo właśnie zapis postfiksowy powoduje, ze nawiasy nie są potrzebne, tzn. w taki sposób przekształca sie zadanie, ze znaki działań matematycznych i liczby ułożone są w sposób priorytetowy - że kolejno oblicza sie je za pomocą automatu ze stosem i nie sa potrzebne nawiasy oraz sprawdzanie priorytetu dzialania.

bear007 2006-12-29 18:10

Artykuł naprawde dobry, przydałoby się jeszcze, żeby ktoś wytłumaczył jak to się dzieje ze w ONP nie są potrzebne nawiasy.

marcin_pcz 2006-02-18 01:45

Nie wierzyłem że to działa, a jednak potrzebowałem takiego programu pod Delphi, zajęło mi to kilka godzin, ale udało się napisać na podstawie tego artykułu program do przetwarzania wyrażeń matematycznych, dodałem nawet różne funkcje: min, max, sin, cos, tan, arcsin, pow, log itp.  ? jakie tylko przyszły mi do głowy, jedno i dwu argumentowe i liczy bez zarzutów:)

szopen 2005-04-20 11:42

\"Czyli równanie: -3+2*(-4+7) należy zapisać jako NEG3+2*(NEG4+7)\"

Niekoniecznie. W parserze mozemy sprawdzic, czy znak \'-\' wystepuje albo na poczatku wyrazenia, albo zaraz po nawiasie otwierającym. Tylko w tych przypadkach bedzie to operator negacji. Odpowiednio formatujac wyjscie (poprzez znaki rozdzielajace, albo zapisywanie juz zanegowanej wartosci) mozemy uniknac problemow zwiazanych z tym jednoargumentowym operatorem.

Marooned 2005-03-23 13:50

możesz używać html w artykułach - więc po co wrzucałeś obrazki zamiast zrobić tabelki? no ale nic już ;)