Evaluate Reverse Polish Notation

mediumSave

MathStackString

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Examples of Reverse Polish Notation:

['2', '1', '+', '3', '*'] yields (2 + 1) * 3 = 9.
['4', '13', '5', '/', '+'] yields 4 + (13 / 5) = 6.6 (evaluated as 6 in integer division).

Your task is to write a function that takes an array of strings representing the postfix expression and returns the evaluation result of that expression.

Example 1

Input

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

Output

Explanation. `(2 + 1) * 3 = 9`

Example 2

Input

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

Output

Explanation. `4 + (13 / 5) = 6` using integer division

Example 3

Input

[
  "10",
  "6",
  "9",
  "3",
  "+",
  "-11",
  "*",
  "/",
  "*",
  "17",
  "+",
  "5",
  "+"
]

Output

Explanation. The expression evaluates step by step as: `10 * (6 / ((9 + 3) * -11)) * 17 + 5 = 22`

Follow-up: Can you improve your solution to handle additional operators like `^` (exponentiation) or `mod`?

Constraints:

- The given tokens are always a valid sequence. - All operations are between two integers. - Division between two numbers truncates towards zero (integer division).

Views: 4