159. Evaluate a Prefix Expression
Core1000 ms256 MBSolved by 0%
In prefix notation the operator comes BEFORE its two operands, so + 2 3
means 2 + 3.
Read n tokens on one line and print the value of the expression.
Division truncates toward zero, and never divides by zero. The expression is always valid.
Constraints - `1 ≤ n ≤ 100000` - Operands fit in a 64-bit integer. - The result fits in a 64-bit integer.
Input
The first line contains an integer n, the number of tokens.
The second line contains n space-separated tokens — integers and the operators + - * / — in prefix order.
Output
Print one integer — the value of the expression.
Input3
+ 2 3
Output5
Noteis the simplest possible expression
Input5
* + 2 3 4
Output20
Notenests one operator inside another
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution