Developers

Evaluate Reverse Polish Notation

MediumStackAlso known as LeetCode 150

You are given a list of tokens that form a valid expression in reverse Polish notation, where each operator follows the two operands it applies to. A token is either an integer (possibly negative, written like "-11") or one of the operators "+", "-", "*" and "/".

Evaluate the expression and return its value. Division of two integers truncates toward zero (so 7 / -2 is -3 and -7 / 2 is -3). The expression is always valid: there is no division by zero, and every intermediate result and the final answer fit in a 32 bit signed integer.

Examples

Input tokens = ["2", "1", "+", "3", "*"]
Output 9
(2 + 1) * 3.
Input tokens = ["4", "13", "5", "/", "+"]
Output 6
4 + (13 / 5) = 4 + 2.
Input tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output 22

Constraints

  • 1 <= tokens.length <= 10,000
  • each token is an integer in the range [-200, 200] or one of + - * /
  • the expression is valid and every intermediate result fits in 32 bits

Stuck? Take one hint at a time

Common mistakes
  • Popping the operands in the wrong order, so that "4 2 /" becomes 2 / 4 and "5 3 -" becomes 3 - 5.
  • Using floor division, which gives -4 for -7 / 2 where the problem wants -3.
  • Treating "-11" as the subtract operator because it starts with a minus sign. Only the one character token "-" is an operator.
  • Recognizing operators with a test such as "is not a digit", which fails on negative numbers.
Questions an interviewer may ask next
  • Read the expression in ordinary (infix) form with brackets and precedence. (The shunting yard method turns it into reverse Polish notation first.)
  • Print the expression back in infix form with the minimum number of brackets.
  • Add a unary minus and a function such as max. How does the stack idea cope with an operator that takes one or three operands?
  • What if the input may be invalid? List what can go wrong (too few operands, leftover numbers, division by zero) and how you would report each.