All problems

Evaluate Reverse Polish Notation

Medium · stack

You are given a list of strings tokens that spells out an arithmetic expression in reverse Polish notation (also called postfix notation). Evaluate it and return the result as an integer.

Each token is either an integer written in decimal (it may have a leading -, such as "-4") or one of the four operators "+", "-", "*" and "/". In this notation an operator comes after its two operands. It takes the two values that come right before it, in the order they were written, and replaces them with the result. For example, ["6", "2", "-"] means 6 - 2, and ["1", "2", "+", "5", "*"] means (1 + 2) * 5.

Division of integers truncates toward zero: 7 / 2 is 3, -7 / 2 is -3 and 7 / -2 is -3.

The expression is always valid, so no division by zero happens and exactly one value is left at the end. Every intermediate result fits in a signed 32-bit integer.

Examples

Example 1

Input: tokens = ["4", "2", "+", "3", "*"]

Output: 18

4 + 2 is 6, and 6 * 3 is 18.

Example 2

Input: tokens = ["9", "2", "-", "-3", "/"]

Output: -2

9 - 2 is 7, and 7 / -3 is -2.33..., which truncates toward zero to -2.

Example 3

Input: tokens = ["7"]

Output: 7

A single number is already the answer.

Constraints