Odwrotna notacja polska

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 + * -

Takt	Wejście	Stos*	Wyjście
1	2	2,#
2	1	1,2,#
3	+	3,#	2 + 1
4	3	3,3,#
5	*	9,#	3 * 3
6	4	4,9,#
7	7	7,4,9,#
8	4	4,7,4,9,#
9	+	11,4,9,#	7 + 4
10	*	44,9,#	4 * 11
11	-	-35,#	9 - 44
12	KONIEC	#	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:

Takt	Wejście	Stos	Wyjście
1	(	(,#
2	2	(,#	2
3	+	+,(,#
4	1	+,(,#	1
5	)	#	+
6	*	*,#
7	3	*,#	3
8	-	-,#	*
9	4	-,#	4
10	*	*,-,#
11	(	(,*,-,#
12	7	(,*,-,#	7
13	+	+,(,*,-,#
14	4	+,(,*,-,#	4
15	)	*,-,#	+
16	KONIEC	-,#	*
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.