Evaluate reverse Polish notation
In postfix order (also called reverse Polish notation), each operator comes after the two values it combines (its operands), not between them. So 3 + 4 is written 3 4 +, and (3 + 4) * 2 is written 3 4 + 2 *. No parentheses are ever needed.
You get an expression in postfix order as a list of strings tokens. Each token is either an integer, such as "12" or "-5", or one of the operators "+", "-", "*" and "/". Return the value of the expression as an int.
- For
-and/, the operand that came first goes on the left:["9", "2", "-"]is 9 - 2 = 7. - Division drops any fraction, which rounds toward zero: 7 / 2 is 3, and -7 / 2 is -3.
You can count on a well-formed expression that never divides by zero. Every value along the way, the answer included, fits in a 32-bit integer: it lies between -231 and 231 - 1.
tokens = ["3", "4", "+", "2", "*"]Output143 + 4 is 7, then 7 * 2 is 14.
tokens = ["10", "3", "/", "5", "-"]Output-210 / 3 is 3 once the fraction is dropped, then 3 - 5 is -2.
tokens = ["-7", "2", "/"]Output-3-7 / 2 is -3.5. Dropping the fraction gives -3, not -4.
1 ≤ len(tokens) ≤ 105
A number token is an integer from -1000 to 1000.
Every intermediate value and the answer are between -231 and 231 - 1.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.