Evaluate Reverse Polish Notation

StackArray

MediumLeetCode #150

20 min

Problem Statement

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

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are +, -, *, and /.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all intermediate calculations can be represented in a 32-bit integer.

Example

Example 1:

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

Input Tokens:

Result:

Output: 9

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

Solution

A stack is the ideal data structure for evaluating Reverse Polish Notation. We iterate through the tokens; if we see a number, we push it onto the stack. If we see an operator, we pop the top two numbers, perform the operation, and push the result back.

Algorithm Steps

Initialize an empty stack to store operands.
Iterate through each token in the input array.
If the token is a number, push it onto the stack.
If the token is an operator (+, -, *, /), pop the top two elements from the stack.
Perform the operation with the two popped numbers. Note the order matters for subtraction and division (second popped is the first operand).
Push the result of the operation back onto the stack.
After iterating through all tokens, the final result is the only element left in the stack.

Tokens:21+3*

Stack:

Start with an empty stack.

Evaluate Reverse Polish Notation Solution


class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(b / a))
            else:
                stack.append(int(c))
        return stack[0]