Evaluate Reverse Polish Notation

mediumFREEStacks & QueuesMicrosoft DSA

Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators: +, -, *, /. Division truncates toward zero.

eval_rpn(tokens) receives tokens as a list of strings; each is an integer (which may be negative, e.g. "-11") or an operator. Return the value of the expression as an integer.

Example

Input

2,1,+,3,*

Output

Reasoning

The input tokens is a sequence of strings read left to right: 2, 1, +, 3, *. Each string is either an integer (possibly negative) or one of the four operators.
In postfix, an operator acts on the two values that come directly before it, where a value is either a number or the result of an earlier operator. Nothing waits on precedence or parentheses.
The first operator is +, applied to $2$ and $1$ : $2 + 1 = 3$ . That result now stands in for the three tokens 2, 1, +.
Next comes 3, then *, which acts on the earlier result $3$ and the new $3$ : $3 \times 3 = 9$ . All tokens are used and exactly one value remains, so the output is the integer 9. In infix this is $(2 + 1) \times 3$ .
Notice that order matters for $-$ and $\div$ : the value that appeared earlier is the left operand. Division truncates toward zero, so $13 \div 5 = 2.6$ becomes $2$ , and $7 \div (-2) = -3.5$ becomes $-3$ , not $-4$ .

Constraints

1 <= len(tokens) <= 10^4
Tokens are integers or operators

Learn this in

FundamentalsDSA Study Plan

More from Microsoft DSA

FizzBuzzeasy Roman to Integereasy Reverse Integermedium Pow(x, n)medium Implement Stack using Queueseasy

Concept primer

Background Knowledge

Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands. This notation is also known as postfix notation. For example, the expression 3 + 4 would be written as 3 4 + in RPN. This notation has several advantages, including the elimination of the need for parentheses to specify the order of operations.

The key concept in evaluating RPN expressions is the use of a stack data structure. A stack is a Last-In-First-Out (LIFO) data structure, meaning that the most recently added element is the first one to be removed. In the context of RPN, a stack can be used to store the operands, and when an operator is encountered, the top two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.

Understanding the order of operations is also crucial when evaluating RPN expressions. Since the operators follow their operands, the order of operations is implicit in the notation. However, when implementing the evaluation algorithm, it's essential to consider the order in which the operators are applied to ensure correct results. For example, in the expression **3 4 + 2 ***, the addition operation is performed first, and then the result is multiplied by 2.

Algorithm/Approach

The general approach to solving this problem involves using a stack-based algorithm to evaluate the RPN expression. The algorithm iterates through the tokens in the expression, and for each token, it checks if it's an operand or an operator. If it's an operand, it's pushed onto the stack. If it's an operator, the top two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty stack to store the operands.
Iterate through the tokens in the RPN expression.
For each token, check if it's an operand or an operator.
If it's an operand, convert it to a number and push it onto the stack.
If it's an operator, pop the top two operands from the stack, perform the operation, and push the result back onto the stack.
After iterating through all the tokens, the final result should be the only element left on the stack.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to handle the case where there are not enough operands on the stack for an operator.
Not checking for division by zero.
Not handling the case where the input expression is invalid (e.g., contains unknown operators or operands).

Time & Space Complexity

The expected time complexity for this problem is O(n), where n is the number of tokens in the RPN expression, since we're iterating through the tokens once. The expected space complexity is also O(n), since in the worst case, we might need to store all the tokens on the stack.

solution.py

Python 3.13

Test results