596. Evaluate Prefix Expression

Given a list of tokens representing a valid prefix (Polish) expression with integer operands and the operators +, -, *, /, evaluate it and return the integer result. Division truncates toward zero. The input is JSON {tokens}.

Input: JSON {tokens}.

Output: Integer — the evaluated result.

Examples

Input: {"tokens":["+","9","*","2","6"]}
Output: 21
Explanation: 9 + (2*6) = 21.

Input: {"tokens":["5"]}
Output: 5
Explanation: A single operand.

Input: {"tokens":["-","+","7","3","2"]}
Output: 8
Explanation: (7+3) - 2 = 8.

Constraints

• 1<=tokens<=10^4
• valid prefix

Asked by