Dla przetwarzania przez komputer wygodnym sposobem zapisu wyrażeń arytmetycznych jest tzw. odwrotna notacja polska (ONP). Zapis w ONP wyrażenia W nazywamy postacią ONP i oznaczamy ją ONP(W).
W ONP operator (dodawania, odejmowania, mnożenia, dzielenia) umieszczamy za jego argumentami, np. 2+5 zapisujemy jako 2 5 +. Dokładniej, postać ONP dla wyrażenia definiujemy rekurencyjnie:
ONP(w) 1. Jeżeli w jest liczbą, to jego postać ONP jest równa w. 2. Jeżeli w ma postać w1 op w2, gdzie op jest operatorem działania, a w1 i w2 wyrażeniami, to ONP(w) jest równe ONP(w1) ONP(w2) op.
Przykład
W = W1 op W2 W1 W2 op ONP(W) ---------------------------------------------- 1 + 2 1 2 + 1 2 + 5 – 7 5 7 – 5 7 – 3 * ( 5 – 7 ) 3 5 – 7 * 3 5 7 - *
Poniżej zapisano pseudokod algorytmu obliczającego wartość wyrażenia zapisanego w ONP:
DANE:
n — liczba całkowita dodatnia,
X[1… n] — wyrażenie w ONP, gdzie X[i] dla 1<=i<=n jest liczbą lub znakiem
ze zbioru {+, –, *}.
WYNIK:
wartość wyrażenia X.
Algorytm:
1. k:=1
2. Dla i=1,2,…,n wykonuj:
a) jeżeli X[i] jest liczbą, to T[k]:=X[i]
w p.p.:
- k:=k-2
- jeżeli X[i]='+': T[k]:=T[k]+T[k+1]
- jeżeli X[i]='-': T[k]:=T[k]-T[k+1]
- jeżeli X[i]='*': T[k]:=T[k]*T[k+1]
b) k:=k+1
3. Zwróć T[1]
Napisz program, który obliczy wartość wyrażenia zapisanego w ONP, w którym wszystkie liczby są jednocyfrowe.
Pierwszy wiersz wejścia zawiera ciąg znaków o długości nie większej niż 50 znaków.
Obliczona wartość wyrażenia.
Dla danych podanych na wejściu:
499362*5+*1+*4+*4+*1+
Poprawną odpowiedzią jest wyjście:
17009
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath string Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :