Algorytm Odwrotnej Notacji Polskiej (ONP) pozwala na zapis działania arytmetycznego bez użycia nawiasów.
Zasada działania algorytmu jest bardzo prosta i opiera się na strukturze zwanej stosem.
Po wykonaniu algorytmu, na stosie pozostanie jedna liczba będąca wynikiem zastosowania algorytmu odwrotnej notacji polskiej.
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) |
2 - (3 - 5) * 3
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 |
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.
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.
Wartość wyrażenia ONP.
5 6 8 4 * + / 2 +
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