MediumArrayMathStack

Evaluate Reverse Polish Notation

1 approach, code in every language

You are given a list of tokens that describe an arithmetic expression written in Reverse Polish Notation (also called postfix notation). Each token is either an integer or one of the operators +, -, *, or /.

In postfix notation an operator comes after its two operands, so there are no parentheses and the order of evaluation is fully determined by the token sequence. Evaluate the expression and return the resulting integer.

Division between two integers truncates toward zero (the fractional part is dropped), and the input is always a valid expression, so every operator will have two operands available and the result fits in a 32-bit signed integer.

Example 1

Input: tokens = ["4","13","5","/","+"]

Output: 6

This evaluates to (4 + (13 / 5)) = (4 + 2) = 6, since 13 / 5 truncates to 2.

Example 2

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

Output: 9

This evaluates to ((2 + 1) * 3) = (3 * 3) = 9.

Constraints

1 <= tokens.length <= 10^4
tokens[i] is either an operator (+, -, *, /) or an integer in the range [-200, 200]
The given expression is always valid and never divides by zero

Operand Stack

Push numbers onto a stack; when an operator appears, pop two operands, apply it, and push the result.

Loading animation…

Intuition

Postfix notation is built for a stack. As you scan left to right, every number you meet is an operand waiting to be used, so you simply push it. When you meet an operator, its two operands are exactly the two most recently pushed values, which sit on top of the stack. You pop them, apply the operator, and push the single result back so it can serve as an operand for a later operator. Order matters for subtraction and division: the value popped first is the right operand and the value popped second is the left operand. When the tokens run out, the stack holds one value, which is the answer.

Algorithm walkthrough

1Create an empty stack that will hold integer operands.
2Iterate through the tokens one by one.
3If a token is an operator, pop the top value as b (right operand) and the next value as a (left operand).
4Compute a op b, using truncation-toward-zero for division, and push the result back onto the stack.
5If a token is a number, parse it to an integer and push it.
6After processing all tokens, the single remaining value on the stack is the final result.

Implementation

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {"+", "-", "*", "/"}
        for token in tokens:
            if token in operators:
                b = stack.pop()
                a = stack.pop()
                if token == "+":
                    stack.append(a + b)
                elif token == "-":
                    stack.append(a - b)
                elif token == "*":
                    stack.append(a * b)
                else:
                    # int() truncates toward zero
                    stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[-1]

Time

O(n)

Space

O(n)

Each token is processed once. The stack can grow to about half the token count in the worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Postfix Tape Total is our own problem on the technique behind Evaluate Reverse Polish Notation: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free