noodleProblems/
Evaluate Reverse Polish Notation
#117

Evaluate Reverse Polish Notation

AlgorithmmediumArrayMathStack

You are given an arithmetic expression in **Reverse Polish Notation** (postfix) as an array of string tokens. Evaluate it and return the resulting integer.

A token is either an integer (possibly negative) or one of the four operators "+", "-", "*", "/". Each operator applies to the two values that immediately precede it.

Notes: - Division between two integers **truncates toward zero** (so 6 / -4 is -1, not -2). - The expression is always valid, every operator has its two operands, and the result fits in a 32-bit signed integer.

Example cases

  • simple add
    in tokens = ["2","1","+","3","*"]
    out 9
    (2 + 1) * 3 = 9.
  • with division
    in tokens = ["4","13","5","/","+"]
    out 6
    13 / 5 = 2 (truncated), then 4 + 2 = 6.
  • nested
    in tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    out 22

Constraints

  • 1 <= tokens.length <= 10^4
  • Each token is "+", "-", "*", "/", or an integer in [-200, 200].
  • The expression is always a valid postfix expression.
Saved
tokens =
["2","1","+","3","*"]