Reverse Polish Calculator

In reverse Polish notation an operator comes after the two numbers it works on, so 3 4 + means 3 + 4 and 3 4 + 5 * means (3 + 4) * 5. Brackets are never needed.

Write eval_rpn(tokens) that takes an expression as a list of strings and returns its value as an integer. A token is either an integer (possibly negative, like "-3") or one of the operators +, -, * and /. Division keeps only the whole-number part, rounding toward zero: 7 / 2 is 3 and -7 / 2 is -3.

Examples

eval_rpn(["3", "4", "+", "5", "*"])  # returns 35
eval_rpn(["2", "3", "4", "*", "+"])  # returns 14
eval_rpn(["7", "-2", "/"])           # returns -3
eval_rpn(["42"])                     # returns 42

In the second example 2 3 4 * + multiplies 3 by 4 first, then adds 2 to the result.

Constraints

• 1 <= len(tokens) <= 10,000
• The expression is always valid and never divides by zero.
• Numbers in the tokens are between -1,000 and 1,000.