Evaluate Reverse Polish Notation

Stacks & Monotonic Stacks, problem 4 of 7

Evaluate Reverse Polish Notation

Medium

LC #150

stackmathexpression

Not attempted yet

tokens is an arithmetic expression in Reverse Polish Notation (postfix): each operator comes after its two operands. Evaluate it and return the integer result.

  • Operators are +, -, * and /.
  • Every other token is an integer (possibly negative, like "-11").
  • Division between integers truncates toward zero (7 / -2 is -3).
  • The expression is always valid and never divides by zero.

Example 1

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: (2 + 1) * 3 = 9

Example 2

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: 4 + (13 / 5) = 4 + 2 = 6

Example 3

Input: tokens = ["10","6","9","3","+","-11",
                 "*","/","*","17","+","5","+"]
Output: 22

Constraints

  • 1 <= len(tokens) <= 2 * 10^5
  • numbers fit in a 32-bit signed integer, and so do all intermediate results

Python

Loading draft…

Test results

10 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 7 hidden

Run examples, then submit all tests.