Odwrotna Notacja Polska

Dopuszczalne operacje: dodawanie +, odejmowani -, mnożenie *, dzielenie /, nawiasy.

Teoria

Zamiana wyrażeń arytmetycznych na odwrotną notację polską (pobierz w C++)

Algorytm zamiany wyrażenia

Analizuj wyrażenie po jednym elemencie (stałej, zmiennej lub ograniczniku).
Jeśli ten element jest:

stałą lub nazwą zmiennej – przekaż go na wyjście;
operatorem:

jeśli priorytet badanego operatora jest wyższy od priorytetu operatora zajmującego szczyt stosu lub jeśli stos jest pusty – dopisz go na stos;
jeśli na szczycie stosu znajduje się operator o wyższym lub równym priorytecie – odczytaj ze stosu i prześlij na wyjście wszystkie operatory o priorytecie wyższym bądź równym aż do wystąpienia na szczycie stosu operatora o priorytecie niższym od priorytetu operatora nadchodzącego z wejścia; element badany dopisz na stos;

nawiasem:

jeśli trafiłeś na nawias otwierający – dopisz go na stos;
jeśli trafiłeś na nawias zamykający: zdejmij wszystkie operatory ze stosu i przekaż je na wyjście aż do trafienia na nawias otwierający; nawiasów nie wypisuj na wyjście.

Jeśli badane wyrażenie

nie zostało wyczerpane – wróć do punktu pierwszego;
zostało wyczerpane – odczytaj wszystkie operatory ze stosu i przekaż je na wyjście automatu.

Aby poprawnie wykonać zadanie należy założyć priorytety występujących w nim operatorów. Dla podstawowych operacji matematycznych mogą one wyglądać tak, jak prezentuje to poniższa tabela.

Operator	Priorytet
(	0
+,-	1
*,/	2

Realizacja algorytmu odwrotnej notacji polskiej przy pomocy stosu

Algorytm obliczania wartości wyrażenia:

Analizuj wyrażenie po jednym elemencie (stałej, zmiennej lub ograniczniku).
Jeśli ten element jest:

stałą lub nazwą zmiennej – dopisz go na stos;
operatorem – zdejmij ze stosu właściwą dla danego operatora ilość argumentów, wykonaj na nich obliczenia, uzyskany wynik dopisz na stos;

Jeśli badane wyrażenie

nie zostało wyczerpane – wróć do punktu pierwszego;
zostało wyczerpane – wartość znajdująca się na stosie to wynik obliczeń.