Postfix Calculator

medium

Old HP calculators used postfix notation: operands first, operator after. "3 4 +" means 3 + 4. No parentheses needed, ever — the order of tokens encodes the whole expression tree.

Given tokens, a list of strings where each token is an integer or one of + - * /, evaluate the expression and return the result as an integer.

Rules: operators apply to the two most recent unconsumed values (the first popped is the right-hand operand); division truncates toward zero (so 6 / -132 is 0, and -7 / 2 is -3); the input is always a valid expression; no division by zero occurs.

Example 1

in tokens = ["2", "1", "+", "3", "*"]

out 9

(2 + 1) * 3 = 9.

Example 2

in tokens = ["4", "13", "5", "/", "+"]

out 6

4 + (13 / 5) = 4 + 2 = 6.

Example 3

in tokens = ["3", "4", "-"]

out -1

Constraints

· 1 <= len(tokens) <= 10^4
· tokens are valid: integers in [-200, 200] or the operators + - * /
· intermediate values fit in a 64-bit integer