Problem B
Miniräknare med postfixnotation, evaluering av infixnotation

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 *"

Sedan ska din miniräknare använda denna postfixuttryck, och evaluera uttrycket samt skriva ut dess värde.

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 evaluerade värdet av infixuttrycket. Ditt svar kommer accepteras om det absoluta skillnaden mellan ditt svar och det korrekta svaret är mindre än $10^{-6}$.

2 + 3

5

4 * 3 - 2

10

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

0.0

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

2.0

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

14.0