Odwrotna Notacja Polska w Pythonie

---

powrót

Algorytm Odwrotnej Notacji Polskiej (ONP) pozwala na zapis działania arytmetycznego bez użycia nawiasów.

Zasada działania

Zasada działania algorytmu jest bardzo prosta i opiera się na strukturze zwanej stosem.

Algorytm

1. Wczytaj wyrażenie
2. Jeśli wczytane wyrażenie jest liczbą, to wrzuć ją na stos
3. Jeśli wyrażenie jest operatorem, to
   1. zdejmij element ze szczytu stosu i zapisz go w zmiennej a
   2. zdejmij kolejny element ze stosu i zapisz go do zmiennej b
   3. wykonaj działanie b operator a i wrzuć wynik na stos (zwróć uwagę, że pierwszą liczbą działania jest liczba zapisana w zmiennej b).
4. Jeśli są elementy do wczytania, to przejdź do kroku pierwszego
5. W przeciwnym razie wypisz zawartość stosu i zakończ algorytm.

Po wykonaniu algorytmu, na stosie pozostanie jedna liczba będąca wynikiem zastosowania algorytmu odwrotnej notacji polskiej.

Przykład 1

Wyznaczymy wartość wyrażenia zapisanego w ONP:

2 3 5 - 3 * -

Kolejne elementy wyrażenia ONP	Operacja	Zawartość stosu
2	Wrzuć liczbę 2 na stos	2
3	Wrzuć liczbę 3 na stos	2 3
5	Wrzuć liczbę 5 na stos	2 3 5
-	Zdejmij liczbę 5 ze stosu, następnie zdejmij liczbę 3 ze stosu, następnie wynik działania 3 - 5 wrzuć na stos	2 -2
3	Wrzuć liczbę 3 na stos	2 -2 3
*	Zdejmij liczbę 3 ze stosu, następnie zdejmij liczbę -2 ze stosu, następnie wynik działania -2 * 3 wrzuć na stos	2 -6
/	Zdejmij liczbę -6 ze stosu, następnie zdejmij liczbę 2 ze stosu, następnie wynik działania 2 - (-6) wrzuć na stos	8 (wynik)

Powyższe wyrażenie w notacji z nawiasami na postać:

2 - (3 - 5) * 3 

Przykłady

Zapis w notacji z nawiasami	Zapis w ONP	Wynik
4 - 7	4 7 -	-3
4*(2 - 8)	4 2 8 - *	-24
(2 + 4)*(4 - 6)	2 4 + 4 6 - *	-12
5*((3 - 7)*2 - 3*(5 + 1)) - 3	5 3 7 - 2 * 3 5 1 + * - * 3 -	-133

Zadanie

Należy wyznaczyć wartość wyrażenia zapisanego w Odwrotnej Notacji Polskiej. W wyrażeniu będą występowały następujące operatory: +, -, * oraz / (dzielenie całkowite) oraz liczby naturalne nie większe niż milion.

Wejście

W pierwszym i jedynym wierszu wyrażenie zapisane w Odwrotnej Notacji Polskiej. Operatory są oddzielone od liczb znakiem spacji. Długość wyrażenia jest krótsza niż 1000 znaków.

Wyjście

Wartość wyrażenia ONP.

Przykład

Wejście:

5 6 8 4 * + / 2 +

Wyjście:

2

#*****************www.algorytm.edu.pl****************
lista = input().split()
stack = [] # strukturę stosu zaimplementujemy na liście
for i in lista:
    if i.isdigit(): #spawdzam, czy wyrażenie jest liczbą
        n = int(i)
        stack.append(n) # jeśli wczytany element jest liczbą, to wrzuć go na stos
    else:
        b = stack.pop() # jeśli wczytany element jest operatorem, to zdejmij ze stosu dwie liczby a i b
        a = stack.pop()
        if i == '*':
            stack.append(a*b) # wynik działania wrzuć na stos
        elif i == '-':
            stack.append(a-b) # wynik działania wrzuć na stos
        elif i == '+':
            stack.append(a+b) # wynik działania wrzuć na stos
        else:
            stack.append(a//b) # wynik działania wrzuć na stos
print(stack.pop()) # wypisz ostatni i jedyny element znajdujący się na stosie