Problem C
Calculator with Postfix Notation, Error Handling

You are tasked with implementing a calculator that uses postfix notation in its internal representation. Postfix notation is a way of writing expressions that makes them more efficient for computers to evaluate compared to the standard infix notation that you have used in mathematics so far.

This calculator handles arithmetic expressions consisting of a limited set of symbols: positive integers, the operators $\texttt{+}, \texttt{-}, \texttt{*}, \texttt{/}$, and left and right parentheses.

In standard infix notation, operators are placed between operands, and parentheses are used to clarify the order of operations. As usual, $\texttt{*}$ and $\texttt{/}$ have higher precedence than $\texttt{+}$ and $\texttt{-}$, parentheses indicate that expressions within them should be evaluated first, and if there are multiple operators with the same precedence, the operations are performed from left to right.

In postfix notation, operators are placed after the operands. Parentheses are unnecessary because the order of operations is determined by the notation itself. Postfix expressions are evaluated by processing operands and operators from left to right. When an operator is encountered, it is applied to the most recently encountered operands.

Here are some examples of expressions in infix form and their corresponding postfix forms:

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

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

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

Once your calculator converts the infix expression to postfix, it should evaluate the postfix expression and print its value.

Input

The input consists of a single line. The input can be an infix expression where each $U_i$ is either an operand (a positive integer), an operator ($\texttt{+}$, $\texttt{-}$, $\texttt{*}$, or $\texttt{/}$), or a parenthesis (left or right).

The infix expression will be space-separated between all $U_i$, and it is guaranteed that the total number of operands, operators, and parentheses is less than 5000, i.e., $N < 5000$. If $U_i$ is an integer, it is also guaranteed that $0 \leq U_i \leq 1000$.

The input may also be invalid, meaning the above conditions are not met. See examples below.

Output

• If the infix expression is invalid, print "Invalid Infix".

• If the infix expression is valid, evaluate its value and print the result. Your answer will be accepted if the absolute difference between your output and the correct answer is less than $10^{-6}$.

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

14.0

2 ( 3 + 4 )

Invalid Infix

4 * 3 - 2

10

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

0.0

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

2.0

1 +

Invalid Infix

24 - a

Invalid Infix

2.3 + 4.1

Invalid Infix

( 1 + 1

Invalid Infix

2 2 2

Invalid Infix