Knowledge Guide
Home › DSA › Stack

medium Evaluate Reverse Polish Notation

Problem Statement

Given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN), evaluate the expression and return the resulting integer value.

Examples

Example 1

Example 2

Example 3

Constraints:

Try it yourself

Try solving this question here:

java

public class Solution {
    // Evaluate RPN expression
    public int evalRPN(String[] tokens) {
        // ToD0: Write Your Code Here.
        return 0;
    }
}
✅ Solution Evaluate Reverse Polish Notation

Problem Statement

Given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN), evaluate the expression and return the resulting integer value.

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand can be an integer or another expression.
  • Division between two integers should truncate towards zero.
  • No division by zero will occur.
  • The input is a valid RPN expression.
  • All results fit within a 32-bit integer.

Examples

Example 1

  • Input: tokens = ["2", "11", "5", "/", "+"]
  • Output: 4
  • Explanation: (11 / 5) = 2, then (2 + 2) = 4.

Example 2

  • Input: tokens = ["2", "3", "11", "+", "*"]
  • Output: 28
  • Explanation: (11 + 3) = 14, then (2 * 14) = 28.

Example 3

  • Input: tokens = ["5", "1", "2", "+", "4", "*", "+", "3", "-"]
  • Output: 14
  • Explanation: (1 + 2) = 3, (3 * 4) = 12, (5 + 12) = 17, (17 - 3) = 14.

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution

To solve this problem, we use a stack to evaluate the Reverse Polish Notation. In RPN, every operator follows all of its operands. We process each token in the input array one by one. When we encounter an operand (number), we push it onto the stack. When we encounter an operator, we pop the required number of operands from the stack, perform the operation, and push the result back onto the stack. This approach ensures that operations are performed in the correct order. Using a stack is efficient here because it allows us to handle the nested structure of the expression naturally.

This approach is effective because it takes advantage of the LIFO (Last In, First Out) nature of stacks, ensuring that each operation uses the most recently encountered operands. It also handles all types of valid RPN expressions without needing to parse or rearrange the input, making it straightforward and reliable.

Step-by-Step Algorithm

  1. Create an empty stack to store intermediate results.
  2. Iterate through each token in the input array tokens:
    • If the token is a number, convert it to an integer and push it onto the stack.
    • If the token is an operator (+, -, *, or /):
      • Pop the top two numbers from the stack. Let's call them b and a (where a is the second popped number and b is the first popped number).
      • Apply the operator to a and b. For example, if the operator is +, calculate a + b.
      • Push the result of the operation back onto the stack.
  3. After processing all tokens, the stack should contain exactly one element. This element is the result of the expression.
  4. Return the value of the single element left in the stack as the result.

Algorithm Walkthrough

Using the input: ["5", "1", "2", "+", "4", "*", "+", "3", "-"]

Initial State

  • Stack: []

Step-by-Step Execution

  1. Token: "5"

    • Action: Push 5 onto the stack.
    • Stack: [5]

  2. Token: "1"

    • Action: Push 1 onto the stack.
    • Stack: [5, 1]

  3. Token: "2"

    • Action: Push 2 onto the stack.
    • Stack: [5, 1, 2]

  4. Token: "+"

    • Action: Pop 2 and 1 from the stack, compute 1 + 2 = 3, push 3 back onto the stack.
    • Stack: [5, 3]

  5. Token: "4"

    • Action: Push 4 onto the stack.
    • Stack: [5, 3, 4]

  6. Token: "*"

    • Action: Pop 4 and 3 from the stack, compute 3 * 4 = 12, push 12 back onto the stack.
    • Stack: [5, 12]

  7. Token: "+"

    • Action: Pop 12 and 5 from the stack, compute 5 + 12 = 17, push 17 back onto the stack.
    • Stack: [17]

  8. Token: "3"

    • Action: Push 3 onto the stack.
    • Stack: [17, 3]

  9. Token: "-"

    • Action: Pop 3 and 17 from the stack, compute 17 - 3 = 14, push 14 back onto the stack.
    • Stack: [14]

Final State

  • Stack: [14]
  • Result: 14

The final value in the stack, 14, is the result of the RPN expression.

Image
Image

Code

java
import java.util.Stack;

public class Solution {

  // Evaluate RPN expression
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();

    // Iterate through each token
    for (String token : tokens) {
      if (isOperator(token)) {
        // Pop two operands
        int b = stack.pop();
        int a = stack.pop();
        // Apply operator and push result back to stack
        stack.push(applyOperator(a, b, token));
      } else {
        // Push number to stack
        stack.push(Integer.parseInt(token));
      }
    }
    // Result is the last remaining item in stack
    return stack.pop();
  }

  // Check if the token is an operator
  private boolean isOperator(String token) {
    return (
      token.equals("+") ||
      token.equals("-") ||
      token.equals("*") ||
      token.equals("/")
    );
  }

  // Apply the operator to two operands
  private int applyOperator(int a, int b, String operator) {
    switch (operator) {
      case "+":
        return a + b;
      case "-":
        return a - b;
      case "*":
        return a * b;
      case "/":
        return a / b;
      default:
        throw new IllegalArgumentException("Invalid operator");
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.evalRPN(new String[] { "2", "11", "5", "/", "+" })); // 4
    System.out.println(sol.evalRPN(new String[] { "2", "3", "11", "+", "*" })); // 28
    System.out.println(
      sol.evalRPN(new String[] { "5", "1", "2", "+", "4", "*", "+", "3", "-" })
    ); // 14
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where n is the number of tokens in the input array. Each token is processed once, and basic stack operations (push and pop) take constant time, .

Space Complexity

The space complexity of the algorithm is , where n is the number of tokens. In the worst case, all tokens are numbers, and we push each onto the stack, resulting in a maximum stack size of n.

🤖 Don't fully get this? Learn it with Claude

Stuck on Evaluate Reverse Polish Notation? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Evaluate Reverse Polish Notation** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Evaluate Reverse Polish Notation** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Evaluate Reverse Polish Notation**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Evaluate Reverse Polish Notation**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Problem 8 Removing Stars From a StSimplify Path →