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 beznawiasowy zapis ONP wyrażenia matematycznego:
DANE:
s — wyrażenie matematyczne,
WYNIK:
wartość ONP(s)
Algorytm:
1. Dla wszystkich znaków z w wyrażeniu s:
a) jeżeli z jest liczbą, to wypisz go na wyjście
b) jeżeli z jest nawiasem otwierającym, to odłóż go na stos
c) jeżeli z jest nawiasem zamykającym, to:
- zdejmij i wypisz ze stosu wszystkie znaki do nawiasu otwierającego,
przy czym nawiasu otwierającego nie wypisuj na wyjście
d) jeżeli z jest działaniem, to:
- dopóki na stosie jest działanie o priorytecie wyższym lub równym, to zdejmij je i wypisz na wyjście
- odłóż działanie z na stos
2. Zdejmij i wypisz wszystkie znaki ze stosu
Napisz program, który wyznaczy notację beznawiasową wyrażenia.
Pierwszy wiersz wejścia zawiera ciąg znaków o długości nie większej niż 50 znaków, składający się z symboli działań +, -, *. /, nawiasów (, ) oraz liter oznaczających niewiadome.
Wyznaczony zapis ONP wyrażenia matematycznego.
Dla danych podanych na wejściu:
(a/b-c)/(a*b-c)
Poprawną odpowiedzią jest wyjście:
ab/c-ab*c-/
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 :