Problem A
Miniräknare med postfixnotation, infixnotation till postfixnotation

Du ska implementera en miniräknare som använder postfixnotation i sin inre representation. Postfixnotation är ett sätt att skriva uttryck på som gör det extra effektivt för datorn att evaluera dem, jämfört med den normala infixnotationen som du hittills använt i matematiken.

Denna miniräknare hanterar aritmetiska uttryck som består av en avgränsad mängd symboler: positiva heltal, operatorerna $\texttt{+}, \texttt{-}, \texttt{*}, \texttt{/}$ samt höger- och vänsterparentes.

I normal infixform befinner sig operatorerna mellan operanderna, och parenteser används för att klargöra i vilken ordning operationerna ska utföras. Som vanligt har $\texttt{*}$ och $\texttt{/}$ högre prioritet än $\texttt{+}$ och $\texttt{-}$, parenteser anger att uttryck däri utvärderas först, och om det finns flera operatorer med samma prioritet så utförs operationerna från vänster till höger.

I postfixform placeras operatorerna efter operanderna. Parenteser behövs ej, utan ordningen på operationerna framgår av notationen. Postfixnotationen beräknas genom att bearbeta operander och operatorer i den ordning de dyker upp, från vänster till höger. När en operator stöts på, utförs operationen på de senaste operanderna i uttrycket.

Nedan följer några exempel på uttryck i dess infixform respektive dess postfixform:

• "2 + 3" $\ \ \rightarrow \ \ $ "2 3 +"

• "14 * ( 2 + 3 )" $\ \ \rightarrow \ \ $ "14 2 3 + *"

• "( ( 3 + 5 * 1 ) / 8) * 14 " $\ \ \rightarrow \ \ $ "3 5 1 * + 8 / 14 *"

Indata

Det kommer finnas en rad av indata. Intadan är ett infixuttryck $U_1 \ldots U_N$, där $U_i$ är antingen en operand (ett positivt heltal), en operator ($\texttt{+}$, $\texttt{-}$, $\texttt{*}$ eller $\texttt{/}$) eller en parentes (vänster- eller högerparentes).

Infixuttrycket kommer vara separerade med mellanslag mellan alla $U_i$, och det är garanterat summan av antalet operander, operatorer och parentser är mindre än 5000, alltså att $N < 5000$. Om $U_i$ är ett heltal, är det även garanterat att $0 \leq U_i \leq 1000$.

I den här uppgiften garanteras att infixuttrycket är giltigt.

Utdata

Skriv ut det givna uttrycket i dess postfixform, med mellanslag mellan alla operander och operatorer.

Förklaring av Exempelfall 1

Postfixformen för "2 + 3" är "2 3 +". Notera dock att postfixformen "3 2 +" ger samma resultat som den givna infixformen, men talen i uttrycket bör skrivas i samma ordning som givet infixformen, och därför är "3 2 +" inte rätt svar.

2 + 3

2 3 +

4 * 3 - 2

4 3 * 2 -

( 3 + 4 ) / 7 + ( 8 / 4 - 9 / 3 )

3 4 + 7 / 8 4 / 9 3 / - +

( ( ( 120 / 5 + 6 ) / 10 * 5 ) + 36 - 1 ) / 25

120 5 / 6 + 10 / 5 * 36 + 1 - 25 /

( ( 3 + 5 * 1 ) / 8 ) * 14

3 5 1 * + 8 / 14 *