Description
Credit: KKOMDASTRO
After the ticket sorting, Nangong gave Sunna the total ticket sales for her to calculate. But since Nangong loves to mess with Sunna, she gave her a weird equation instead of just the final ticket sales. Your mission now is to write a simple calculator to help Sunna calculate the weird equation.
In fact, the equation Nangong gave was written in Prefix Notation.
In everyday math, we write expressions in infix notation, where the operator sits between its two operands:
$5 + 6$
$(5 * 6) - 7$
This is natural for humans to read, but awkward for a computer to parse — it has to worry about operator precedence (does * happen before -?) and parentheses to disambiguate grouping.
Prefix notation solves this by placing the operator before its operands:
$+$ $5$ $6$ → $5 + 6$
$-$ $*$ $5$ $6$ $7$→ $(5 * 6) - 7$
An expression is either a number or an operator followed by two expressions.
For example, in $-$ $+$ $1$ $2$ $/$ $*$ $3$ $6$ $2$, the operator $-$ takes $(+$ $1$ $2)$ and $(/$ $*$ $3$ $6$ $2)$, so the value is $(1 + 2) - ((3 * 6) / 2) = -6$. The four operators are always binary.
Because the operator always comes first and each operator takes a fixed number of operands (two, for the basic arithmetic operators), there is never any ambiguity about order of operations, and no parentheses are ever needed.
Input
A single line containing a valid prefix-notation arithmetic expression. Tokens (operators and numbers) are separated by whitespace. You may assume:
- The supported operators are $+$, $-$, $*$, and $/$.
- All operands are non-negative integers. The result and intermediate values may be negative.
- No need to handle malformed input.
- Every division in the input is exact, and the divisor is never $0$.
Output
Print the result as a single integer