150. Evaluate Reverse Polish Notation - Explanation

Description

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

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.
The operators include '+', '-', '*', and '/'.
Assume that division between integers always truncates toward zero.

Example 1:

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

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

1 <= tokens.length <= 1000.
tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would involve repeatedly finding an operator + - * / in the array and modifying the array by computing the result for that operator and two operands to its left. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use a data structure to handle operations efficiently.

Hint 2

We can use a stack. We iterate through the array, and if we encounter a number, we push it onto the stack. If we encounter an operator, we pop two elements from the stack, treat them as operands, and solve the equation using the current operator. Then, we push the result back onto the stack. Why does this work?

Hint 3

As the array has postfix expression, stack helps us to maintain the correct order of operations by ensuring that we always use the most recent operands (those closest to the operator) when performing the operation. After the iteration, the final result is left in the stack.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Essential for storing operands and applying operators in LIFO order
String Parsing - Converting string tokens to integers and identifying operators
Basic Arithmetic Operations - Handling addition, subtraction, multiplication, and integer division with truncation toward zero
Postfix Expression Evaluation - Understanding that operators apply to the two most recent operands

1. Brute Force

Intuition

Reverse Polish Notation (RPN) evaluates expressions without parentheses by applying each operator to the two most recent numbers.
The brute-force idea is to repeatedly scan the list until we find an operator.
When we do, we take the two numbers before it, compute the result, and replace all three tokens with the result.
We continue compressing the list this way until only one value remains—the final answer.
This approach works but is slow because we repeatedly rebuild and rescan the list.

Algorithm

While more than one token exists:
- Scan the list from left to right.
- When an operator is found:
  - Take the two numbers immediately before it.
  - Apply the operator to compute a result.
  - Replace the pattern [number, number, operator] with the computed value.
  - Restart scanning.
When only one token is left, return it as the final result.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        while len(tokens) > 1:
            for i in range(len(tokens)):
                if tokens[i] in "+-*/":
                    a = int(tokens[i-2])
                    b = int(tokens[i-1])
                    if tokens[i] == '+':
                        result = a + b
                    elif tokens[i] == '-':
                        result = a - b
                    elif tokens[i] == '*':
                        result = a * b
                    elif tokens[i] == '/':
                        result = int(a / b)
                    tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                    break
        return int(tokens[0])

public class Solution {
    public int evalRPN(String[] tokens) {
        List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));

        while (tokenList.size() > 1) {
            for (int i = 0; i < tokenList.size(); i++) {
                String token = tokenList.get(i);

                if ("+-*/".contains(token)) {
                    int a = Integer.parseInt(tokenList.get(i - 2));
                    int b = Integer.parseInt(tokenList.get(i - 1));
                    int result = 0;

                    if (token.equals("+")) {
                        result = a + b;
                    } else if (token.equals("-")) {
                        result = a - b;
                    } else if (token.equals("*")) {
                        result = a * b;
                    } else if (token.equals("/")) {
                        result = a / b;
                    }

                    tokenList.set(i - 2, String.valueOf(result));
                    tokenList.remove(i);
                    tokenList.remove(i - 1);
                    break;
                }
            }
        }
        return Integer.parseInt(tokenList.get(0));
    }
}

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        while (tokens.size() > 1) {
            for (int i = 0; i < tokens.size(); i++) {
                if (tokens[i] == "+"
                    || tokens[i] == "-"
                    || tokens[i] == "*"
                    || tokens[i] == "/")
                {
                    int a = stoi(tokens[i - 2]);
                    int b = stoi(tokens[i - 1]);
                    int result = 0;
                    if (tokens[i] == "+") result = a + b;
                    else if (tokens[i] == "-") result = a - b;
                    else if (tokens[i] == "*") result = a * b;
                    else if (tokens[i] == "/") result = a / b;

                    tokens.erase(tokens.begin() + i - 2, tokens.begin() + i + 1);
                    tokens.insert(tokens.begin() + i - 2, to_string(result));
                    break;
                }
            }
        }
        return stoi(tokens[0]);
    }
};

class Solution {
    evalRPN(tokens) {
        while (tokens.length > 1) {
            for (let i = 0; i < tokens.length; i++) {
                if ('+-*/'.includes(tokens[i])) {
                    const a = parseInt(tokens[i - 2]);
                    const b = parseInt(tokens[i - 1]);
                    let result;
                    if (tokens[i] === '+') result = a + b;
                    else if (tokens[i] === '-') result = a - b;
                    else if (tokens[i] === '*') result = a * b;
                    else if (tokens[i] === '/') result = Math.trunc(a / b);

                    tokens.splice(i - 2, 3, result.toString());
                    break;
                }
            }
        }
        return parseInt(tokens[0]);
    }
}

public class Solution {
    public int EvalRPN(string[] tokens) {
        List<string> tokenList = new List<string>(tokens);

        while (tokenList.Count > 1) {
            for (int i = 0; i < tokenList.Count; i++) {
                if ("+-*/".Contains(tokenList[i])) {
                    int a = int.Parse(tokenList[i - 2]);
                    int b = int.Parse(tokenList[i - 1]);
                    int result = 0;
                    switch (tokenList[i]) {
                        case "+":
                            result = a + b;
                            break;
                        case "-":
                            result = a - b;
                            break;
                        case "*":
                            result = a * b;
                            break;
                        case "/":
                            result = a / b;
                            break;
                    }
                    tokenList.RemoveRange(i - 2, 3);
                    tokenList.Insert(i - 2, result.ToString());
                    break;
                }
            }
        }
        return int.Parse(tokenList[0]);
    }
}

class Solution {
   fun evalRPN(tokens: Array<String>): Int {
       val A = tokens.toMutableList()

       while (A.size > 1) {
           for (i in A.indices) {
               if (A[i] in setOf("+", "-", "*", "/")) {
                   val a = A[i-2].toInt()
                   val b = A[i-1].toInt()
                   val result = when (A[i]) {
                       "+" -> a + b
                       "-" -> a - b
                       "*" -> a * b
                       else -> a / b
                   }

                   val temp = A.slice(0..i-3) +
                             result.toString() +
                             A.slice(i+1..A.lastIndex)
                   A.clear()
                   A.addAll(temp)
                   break
               }
           }
       }

       return A[0].toInt()
   }
}

class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var tokens = tokens

        while tokens.count > 1 {
            for i in 0..<tokens.count {
                if "+-*/".contains(tokens[i]) {
                    let a = Int(tokens[i-2])!
                    let b = Int(tokens[i-1])!
                    var result = 0

                    if tokens[i] == "+" {
                        result = a + b
                    } else if tokens[i] == "-" {
                        result = a - b
                    } else if tokens[i] == "*" {
                        result = a * b
                    } else if tokens[i] == "/" {
                        result = Int(a / b)
                    }

                    tokens = Array(tokens[0..<(i-2)]) + [String(result)] + Array(tokens[(i+1)...])
                    break
                }
            }
        }

        return Int(tokens[0])!
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Doubly Linked List

Intuition

In Reverse Polish Notation, every operator works on the two most recent numbers before it.
A doubly linked list lets us move both left and right easily, so when we find an operator, we can quickly reach the two numbers before it.

The idea is:

Build a doubly linked list of all tokens (numbers and operators).
Walk through the list:
- When we see an operator, we look at the previous two nodes (the two operands),
  compute the result, and replace those three nodes (left, right, operator)
  with a single node containing the result.
We keep doing this until we've processed all operators and are left with just one value.

This behaves like the usual RPN evaluation but uses linked list navigation instead of a stack.

Algorithm

Create a doubly linked list from the tokens in order.
Set a pointer curr to the head of the list.
While the list still needs evaluation:
- If curr is an operator:
  - Let the two nodes before curr be the left and right operands.
  - Compute the result of left (op) right.
  - Replace the three nodes (left, right, operator) with a single node holding the result:
    - Relink the prev and next pointers around them.
    - Set curr to this result node.
- Move curr to the next node and continue.
When only one node with a number remains, return its value as the final result.

class DoublyLinkedList:
    def __init__(self, val, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        head = DoublyLinkedList(tokens[0])
        curr = head

        for i in range(1, len(tokens)):
            curr.next = DoublyLinkedList(tokens[i], prev=curr)
            curr = curr.next

        while head is not None:
            if head.val in "+-*/":
                l = int(head.prev.prev.val)
                r = int(head.prev.val)
                if head.val == '+':
                    res = l + r
                elif head.val == '-':
                    res = l - r
                elif head.val == '*':
                    res = l * r
                else:
                    res = int(l / r)

                head.val = str(res)
                head.prev = head.prev.prev.prev
                if head.prev is not None:
                    head.prev.next = head

            ans = int(head.val)
            head = head.next

        return ans

public class DoublyLinkedList {
    String val;
    DoublyLinkedList next;
    DoublyLinkedList prev;

    DoublyLinkedList(String val, DoublyLinkedList next, DoublyLinkedList prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

public class Solution {
    public int evalRPN(String[] tokens) {
        DoublyLinkedList head = new DoublyLinkedList(tokens[0], null, null);
        DoublyLinkedList curr = head;

        for (int i = 1; i < tokens.length; i++) {
            curr.next = new DoublyLinkedList(tokens[i], null, curr);
            curr = curr.next;
        }

        int ans = 0;
        while (head != null) {
            if ("+-*/".contains(head.val)) {
                int l = Integer.parseInt(head.prev.prev.val);
                int r = Integer.parseInt(head.prev.val);
                int res = 0;
                if (head.val.equals("+")) {
                    res = l + r;
                } else if (head.val.equals("-")) {
                    res = l - r;
                } else if (head.val.equals("*")) {
                    res = l * r;
                } else {
                    res = l / r;
                }

                head.val = String.valueOf(res);
                head.prev = head.prev.prev.prev;
                if (head.prev != null) {
                    head.prev.next = head;
                }
            }

            ans = Integer.parseInt(head.val);
            head = head.next;
        }

        return ans;
    }
}

class DoublyLinkedList {
public:
    string val;
    DoublyLinkedList* next;
    DoublyLinkedList* prev;

    DoublyLinkedList(string val, DoublyLinkedList* next = nullptr,
                        DoublyLinkedList* prev = nullptr) {
        this->val = val;
        this->next = next;
        this->prev = prev;
    }
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        DoublyLinkedList* head = new DoublyLinkedList(tokens[0]);
        DoublyLinkedList* curr = head;

        for (int i = 1; i < tokens.size(); i++) {
            curr->next = new DoublyLinkedList(tokens[i], nullptr, curr);
            curr = curr->next;
        }

        int ans = 0;
        while (head != nullptr) {
            if (head->val == "+" ||
                 head->val == "-" ||
                 head->val == "*" ||
                 head->val == "/")
            {
                int l = stoi(head->prev->prev->val);
                int r = stoi(head->prev->val);
                int res = 0;
                if (head->val == "+") {
                    res = l + r;
                } else if (head->val == "-") {
                    res = l - r;
                } else if (head->val == "*") {
                    res = l * r;
                } else {
                    res = l / r;
                }

                head->val = to_string(res);
                head->prev = head->prev->prev->prev;
                if (head->prev != nullptr) {
                    head->prev->next = head;
                }
            }

            ans = stoi(head->val);
            head = head->next;
        }

        return ans;
    }
};

class DoublyLinkedList {
    constructor(val, next = null, prev = null) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class Solution {
    /**
     * @param {string[]} tokens
     * @return {number}
     */
    evalRPN(tokens) {
        let head = new DoublyLinkedList(tokens[0]);
        let curr = head;

        for (let i = 1; i < tokens.length; i++) {
            curr.next = new DoublyLinkedList(tokens[i], null, curr);
            curr = curr.next;
        }

        let ans = 0;
        while (head !== null) {
            if ('+-*/'.includes(head.val)) {
                let l = parseInt(head.prev.prev.val);
                let r = parseInt(head.prev.val);
                let res = 0;
                if (head.val === '+') {
                    res = l + r;
                } else if (head.val === '-') {
                    res = l - r;
                } else if (head.val === '*') {
                    res = l * r;
                } else {
                    res = Math.trunc(l / r);
                }

                head.val = res.toString();
                head.prev = head.prev.prev.prev;
                if (head.prev !== null) {
                    head.prev.next = head;
                }
            }

            ans = parseInt(head.val);
            head = head.next;
        }

        return ans;
    }
}

public class DoublyLinkedList {
    public string val;
    public DoublyLinkedList next;
    public DoublyLinkedList prev;

    public DoublyLinkedList(string val, DoublyLinkedList next = null,
                            DoublyLinkedList prev = null) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

public class Solution {
    public int EvalRPN(string[] tokens) {
        DoublyLinkedList head = new DoublyLinkedList(tokens[0]);
        DoublyLinkedList curr = head;

        for (int i = 1; i < tokens.Length; i++) {
            curr.next = new DoublyLinkedList(tokens[i], null, curr);
            curr = curr.next;
        }

        int ans = 0;
        while (head != null) {
            if ("+-*/".Contains(head.val)) {
                int l = int.Parse(head.prev.prev.val);
                int r = int.Parse(head.prev.val);
                int res = 0;
                if (head.val == "+") {
                    res = l + r;
                } else if (head.val == "-") {
                    res = l - r;
                } else if (head.val == "*") {
                    res = l * r;
                } else {
                    res = l / r;
                }

                head.val = res.ToString();
                head.prev = head.prev.prev.prev;
                if (head.prev != null) {
                    head.prev.next = head;
                }
            }

            ans = int.Parse(head.val);
            head = head.next;
        }

        return ans;
    }
}

type DoublyLinkedList struct {
    val  string
    next *DoublyLinkedList
    prev *DoublyLinkedList
}

func evalRPN(tokens []string) int {
    head := &DoublyLinkedList{val: tokens[0]}
    curr := head

    for i := 1; i < len(tokens); i++ {
        newNode := &DoublyLinkedList{val: tokens[i], prev: curr}
        curr.next = newNode
        curr = curr.next
    }

    for head != nil {
        if head.val == "+" || head.val == "-" || head.val == "*" || head.val == "/" {
            l, _ := strconv.Atoi(head.prev.prev.val)
            r, _ := strconv.Atoi(head.prev.val)

            var res int
            switch head.val {
            case "+":
                res = l + r
            case "-":
                res = l - r
            case "*":
                res = l * r
            case "/":
                res = l / r
            }

            head.val = strconv.Itoa(res)
            head.prev = head.prev.prev.prev
            if head.prev != nil {
                head.prev.next = head
            }
        }

        head = head.next
    }

    ans, _ := strconv.Atoi(curr.val)
    return ans
}

class DoublyLinkedList(
   var value: String,
   var next: DoublyLinkedList? = null,
   var prev: DoublyLinkedList? = null
)

class Solution {
   fun evalRPN(tokens: Array<String>): Int {
       val head = DoublyLinkedList(tokens[0])
       var curr = head

       for (i in 1 until tokens.size) {
           val newNode = DoublyLinkedList(tokens[i], prev = curr)
           curr.next = newNode
           curr = newNode
       }

       var ptr: DoublyLinkedList? = head
       while (ptr != null) {
           if (ptr.value in setOf("+", "-", "*", "/")) {
               val l = ptr.prev!!.prev!!.value.toInt()
               val r = ptr.prev!!.value.toInt()

               val res = when (ptr.value) {
                   "+" -> l + r
                   "-" -> l - r
                   "*" -> l * r
                   else -> l / r
               }

               ptr.value = res.toString()
               ptr.prev = ptr.prev!!.prev!!.prev
               ptr.prev?.next = ptr
           }

           ptr = ptr.next
       }

       return curr.value.toInt()
   }
}

class DoublyLinkedList {
    var val: String
    var next: DoublyLinkedList?
    var prev: DoublyLinkedList?

    init(val: String, next: DoublyLinkedList? = nil, prev: DoublyLinkedList? = nil) {
        self.val = val
        self.next = next
        self.prev = prev
    }
}

class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var head: DoublyLinkedList? = DoublyLinkedList(val: tokens[0])
        var curr = head

        for i in 1..<tokens.count {
            curr!.next = DoublyLinkedList(val: tokens[i], prev: curr)
            curr = curr!.next
        }

        var ans = 0

        while head != nil {
            if "+-*/".contains(head!.val) {
                let l = Int(head!.prev!.prev!.val)!
                let r = Int(head!.prev!.val)!
                var res: Int

                if head!.val == "+" {
                    res = l + r
                } else if head!.val == "-" {
                    res = l - r
                } else if head!.val == "*" {
                    res = l * r
                } else {
                    res = l / r
                }

                head!.val = String(res)
                head!.prev = head!.prev!.prev!.prev

                if head!.prev != nil {
                    head!.prev!.next = head
                }
            }

            ans = Int(head!.val)!
            head = head!.next
        }

        return ans
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Recursion

Intuition

Reverse Polish Notation works naturally with recursion because every operator applies to the two most recent values that come before it.
If we process the expression from the end, every time we see:

a number → it is simply returned as a value
an operator → we recursively evaluate the two values that belong to it

This creates a natural evaluation tree:

Each operator becomes a recursive call,
Each number becomes a base case,
And the final return value is the fully evaluated expression.

This approach is clean, elegant, and mirrors the structure of RPN itself.

Algorithm

Start from the end of the token list.
Recursively:
- Pop a token.
- If it is a number, return it.
- If it is an operator:
  - Recursively compute the right operand.
  - Recursively compute the left operand.
  - Apply the operator to both results.
  - Return the computed value.
The first completed call returns the final answer.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        def dfs():
            token = tokens.pop()
            if token not in "+-*/":
                return int(token)

            right = dfs()
            left = dfs()

            if token == '+':
                return left + right
            elif token == '-':
                return left - right
            elif token == '*':
                return left * right
            elif token == '/':
                return int(left / right)

        return dfs()

public class Solution {
    public int evalRPN(String[] tokens) {
        List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));
        return dfs(tokenList);
    }

    private int dfs(List<String> tokens) {
        String token = tokens.remove(tokens.size() - 1);

        if (!"+-*/".contains(token)) {
            return Integer.parseInt(token);
        }

        int right = dfs(tokens);
        int left = dfs(tokens);

        switch (token) {
            case "+":
                return left + right;
            case "-":
                return left - right;
            case "*":
                return left * right;
            case "/":
                return left / right;
        }

        return 0;
    }
}

class Solution {
public:
    int dfs(vector<string>& tokens) {
        string token = tokens.back();
        tokens.pop_back();

        if (token != "+" && token != "-" &&
             token != "*" && token != "/")
        {
            return stoi(token);
        }

        int right = dfs(tokens);
        int left = dfs(tokens);

        if (token == "+") {
            return left + right;
        } else if (token == "-") {
            return left - right;
        } else if (token == "*") {
            return left * right;
        } else {
            return left / right;
        }
    }

    int evalRPN(vector<string>& tokens) {
        return dfs(tokens);
    }
};

class Solution {
    /**
     * @param {string[]} tokens
     * @return {number}
     */
    evalRPN(tokens) {
        /**
         * @return {number}
         */
        const dfs = () => {
            const token = tokens.pop();
            if (!'+-*/'.includes(token)) {
                return parseInt(token);
            }

            const right = dfs();
            const left = dfs();

            if (token === '+') {
                return left + right;
            } else if (token === '-') {
                return left - right;
            } else if (token === '*') {
                return left * right;
            } else {
                return Math.trunc(left / right);
            }
        };

        return dfs();
    }
}

public class Solution {
    public int EvalRPN(string[] tokens) {
        List<string> tokenList = new List<string>(tokens);
        return DFS(tokenList);
    }

    public int DFS(List<string> tokens) {
        string token = tokens[tokens.Count - 1];
        tokens.RemoveAt(tokens.Count - 1);

        if (token != "+" && token != "-" &&
         token != "*" && token != "/") {
            return int.Parse(token);
        }

        int right = DFS(tokens);
        int left = DFS(tokens);

        if (token == "+") {
            return left + right;
        } else if (token == "-") {
            return left - right;
        } else if (token == "*") {
            return left * right;
        } else {
            return left / right;
        }
    }
}

func evalRPN(tokens []string) int {
    index := len(tokens) - 1

    var dfs func() int
    dfs = func() int {
        token := tokens[index]
        index--

        if token != "+" && token != "-" && token != "*" && token != "/" {
            val, _ := strconv.Atoi(token)
            return val
        }

        right := dfs()
        left := dfs()

        switch token {
        case "+":
            return left + right
        case "-":
            return left - right
        case "*":
            return left * right
        default:
            return left / right
        }
    }

    return dfs()
}

class Solution {
    private var index = 0

    fun evalRPN(tokens: Array<String>): Int {
        index = tokens.size - 1

        fun dfs(): Int {
            val token = tokens[index]
            index--

            if (token !in setOf("+", "-", "*", "/")) {
                return token.toInt()
            }

            val right = dfs()
            val left = dfs()

            return when (token) {
                "+" -> left + right
                "-" -> left - right
                "*" -> left * right
                else -> left / right
            }
        }

        return dfs()
    }
}

class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var tokens = tokens

        func dfs() -> Int {
            let token = tokens.removeLast()
            if let num = Int(token) {
                return num
            }

            let right = dfs()
            let left = dfs()

            switch token {
                case "+": return left + right
                case "-": return left - right
                case "*": return left * right
                case "/": return left / right
                default: return 0
            }
        }

        return dfs()
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Stack

Intuition

A stack fits Reverse Polish Notation perfectly because the most recent numbers are always the ones used next.
As we scan the tokens:

When we see a number, we push it onto the stack.
When we see an operator, we pop the top two numbers, apply the operation, and push the result back.

This way, the stack always holds the intermediate results, and the final remaining value is the answer.
It is clean, efficient, and directly follows how RPN is meant to be evaluated.

Algorithm

Create an empty stack.
For each token:
- If it is a number, convert it to an integer and push it onto the stack.
- If it is an operator:
  - Pop the top two numbers.
  - Apply the operator in the correct order.
  - Push the result back onto the stack.
After processing all tokens, the stack contains exactly one value — return it.

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(float(b) / a))
            else:
                stack.append(int(c))
        return stack[0]

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String c : tokens) {
            if (c.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (c.equals("-")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b - a);
            } else if (c.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (c.equals("/")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b / a);
            } else {
                stack.push(Integer.parseInt(c));
            }
        }
        return stack.pop();
    }
}

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stack;
        for (const string& c : tokens) {
            if (c == "+") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b + a);
            } else if (c == "-") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b - a);
            } else if (c == "*") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b * a);
            } else if (c == "/") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b / a);
            } else {
                stack.push(stoi(c));
            }
        }
        return stack.top();
    }
};

class Solution {
    /**
     * @param {string[]} tokens
     * @return {number}
     */
    evalRPN(tokens) {
        const stack = [];
        for (const c of tokens) {
            if (c === '+') {
                stack.push(stack.pop() + stack.pop());
            } else if (c === '-') {
                const a = stack.pop();
                const b = stack.pop();
                stack.push(b - a);
            } else if (c === '*') {
                stack.push(stack.pop() * stack.pop());
            } else if (c === '/') {
                const a = stack.pop();
                const b = stack.pop();
                stack.push(Math.trunc(b / a));
            } else {
                stack.push(parseInt(c));
            }
        }
        return stack.pop();
    }
}

public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> stack = new Stack<int>();
        foreach (string c in tokens) {
            if (c == "+") {
                stack.Push(stack.Pop() + stack.Pop());
            } else if (c == "-") {
                int a = stack.Pop();
                int b = stack.Pop();
                stack.Push(b - a);
            } else if (c == "*") {
                stack.Push(stack.Pop() * stack.Pop());
            } else if (c == "/") {
                int a = stack.Pop();
                int b = stack.Pop();
                stack.Push((int) ((double) b / a));
            } else {
                stack.Push(int.Parse(c));
            }
        }
        return stack.Pop();
    }
}

func evalRPN(tokens []string) int {
   stack := make([]int, 0)

   for _, token := range tokens {
       switch token {
       case "+":
           a := stack[len(stack)-1]
           b := stack[len(stack)-2]
           stack = stack[:len(stack)-2]
           stack = append(stack, b+a)
       case "-":
           a := stack[len(stack)-1]
           b := stack[len(stack)-2]
           stack = stack[:len(stack)-2]
           stack = append(stack, b-a)
       case "*":
           a := stack[len(stack)-1]
           b := stack[len(stack)-2]
           stack = stack[:len(stack)-2]
           stack = append(stack, b*a)
       case "/":
           a := stack[len(stack)-1]
           b := stack[len(stack)-2]
           stack = stack[:len(stack)-2]
           stack = append(stack, b/a)
       default:
           num, _ := strconv.Atoi(token)
           stack = append(stack, num)
       }
   }

   return stack[0]
}

class Solution {
    fun evalRPN(tokens: Array<String>): Int {
        val stack = ArrayDeque<Int>()

        for (token in tokens) {
            when (token) {
                "+" -> {
                    val a = stack.removeLast()
                    val b = stack.removeLast()
                    stack.addLast(b + a)
                }
                "-" -> {
                    val a = stack.removeLast()
                    val b = stack.removeLast()
                    stack.addLast(b - a)
                }
                "*" -> {
                    val a = stack.removeLast()
                    val b = stack.removeLast()
                    stack.addLast(b * a)
                }
                "/" -> {
                    val a = stack.removeLast()
                    val b = stack.removeLast()
                    stack.addLast(b / a)
                }
                else -> stack.addLast(token.toInt())
            }
        }

        return stack.last()
    }
}

class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var stack = [Int]()

        for c in tokens {
            switch c {
                case "+":
                    stack.append(stack.removeLast() + stack.removeLast())
                case "-":
                    let a = stack.removeLast()
                    let b = stack.removeLast()
                    stack.append(b - a)
                case "*":
                    stack.append(stack.removeLast() * stack.removeLast())
                case "/":
                    let a = stack.removeLast()
                    let b = stack.removeLast()
                    stack.append(b / a)
                default:
                    stack.append(Int(c)!)
            }
        }
        return stack[0]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Wrong Operand Order for Subtraction and Division

For subtraction and division, the order matters: the second-to-last operand is the left operand, and the last operand is the right operand. When you pop from a stack, the first pop gives you the right operand (b), and the second pop gives you the left operand (a). Computing b - a or b / a instead of a - b or a / b will produce incorrect results.

Incorrect Integer Division Truncation

Division in RPN truncates toward zero, not toward negative infinity. In languages like Python 2 or when using floor division, -7 / 2 gives -4, but the correct RPN result is -3. You must use truncation toward zero, such as int(a / b) in Python 3 or Math.trunc() in JavaScript.

Treating Negative Numbers as Operators

Tokens like "-3" are valid negative numbers, not the subtraction operator followed by "3". When checking if a token is an operator, you cannot simply check if the first character is -. Instead, check if the token equals exactly "+", "-", "*", or "/", or verify that the token has length 1 when it starts with an operator character.