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 - *
Można w prosty sposób sprawdzić, czy wyrażenie w jest poprawnym wyrażeniem zapisanym w ONP - wystarczy, aby dla każdego niepustego początkowego fragmentu wyrażenia w, ilość liczb występujących w tym fragmencie była większa od ilości działań, zaś w całym wyrażeniu spełniony był dodatkowo jeszcze jeden warunek.
Napisz program, który dla podanego wyrażenia w, w którym wszystkie liczby są cyframi sprawdzi, czy wyrażenie to jest poprawnie zapisane w ONP.
Pierwszy wiersz wejścia zawiera ciąg znaków o długości nie większej niż 50 znaków.
Słowo TAK gdy wyrażenie jest poprawne lub najkrótszy początkowy fragment wyrażenia, którey nie jest poprawnym zapisem ONP.
Dla danych podanych na wejściu:
258562*15++*2+*4+**
Poprawną odpowiedzią jest wyjście:
TAK
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 :