Evaluate Reverse Polish Notation

medium

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation.

Evaluate the expression and return an integer representing its value.

Note that division between two integers should truncate toward zero, and the given expression is always valid.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

9

Explanation: ((2 + 1) * 3) = 9

Input

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

Expected Output

6

Explanation: (4 + (13 / 5)) = 6

1 <= tokens.length <= 10^4
tokens[i] is either an operator (+, -, *, /) or an integer in the range [-200, 200].

Hint 1 — click to reveal

RPN is designed for a stack — that is the whole point of the notation.

Hint 2 — click to reveal

Order matters for - and /: the first value popped is the right-hand operand.

Java Compiler