Evaluate Reverse Polish Notation

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

What to notice first

• In RPN, operators come after their operands: 3 4 + means 3 + 4 = 7
• A stack naturally models this: push operands, pop two operands when you see an operator
• Order matters for - and /: the first pop is the second operand
• Division truncates towards zero (not floor division)

Examples

Input	Output	Explanation
["2", "1", "+", "3", "*"]	9	(2 + 1) * 3 = 3 * 3 = 9
["4", "13", "5", "/", "+"]	6	4 + (13 / 5) = 4 + 2 = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]	22	Complex nested operations = 22
["3", "4", "+"]	7	3 + 4 = 7
["15"]	15	Single number is valid

Constraints

• 1 <= tokens.length <= 10^4
• Each token is either an operator or a valid integer in range [-200, 200]
• The input guarantees a valid RPN expression

Real-World Applications

Where this pattern appears

• Calculator implementations — many pocket calculators use RPN to avoid parentheses
• Compiler expression evaluation — intermediate code often uses postfix notation
• Spreadsheet formula engines — some internal representations use RPN
• Undo/redo in editors — operations stored in postfix order for efficient processing

Complexity Comparison

Approach	Time	Space	Best When
Stack	O(n)	O(n)	Straightforward iterative approach; most common
Recursive	O(n)	O(n)	You prefer recursion or need to understand the call stack visually

Both are optimal and equally valid.

Most Common

Stack-Based

O(n) time · O(n) space

Alternative

Recursive

O(n) time · O(n) space

Approach 1: Stack-Based Evaluation (Recommended)

★ Recommended

Iterate through tokens. Push operands onto the stack. When you see an operator, pop the required operands, compute, and push the result back.

The key insight: the stack automatically handles operator precedence because RPN is unambiguous — there are no parentheses to parse.

⏱ Time O(n) Single pass through tokens 💾 Space O(n) Stack size proportional to expression depth

Step-by-step Example

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

Step	Token	Stack (before)	Action	Stack (after)
1	"2"	[]	Push 2	[2]
2	"1"	[2]	Push 1	[2, 1]
3	"+"	[2, 1]	Pop 1, 2 → 2+1=3	[3]
4	"3"	[3]	Push 3	[3, 3]
5	"*"	[3, 3]	Pop 3, 3 → 3*3=9	[9]
Result	—	—	—	9

Animated walkthrough

How the stack evaluates RPN expressions

Watch how operands are pushed and operators pop and compute. Notice the order of operations naturally flows from left to right.

Back Autoplay Next Reset

Step 1 of 6 Target: RPN

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function evaluateRpn(tokens):
    stack = []
    for token in tokens:
        if token is an operator:
            b = stack.pop()
            a = stack.pop()
            result = applyOperator(a, token, b)
            stack.push(result)
        else:
            stack.push(int(token))
    return stack[0]

Solution Code

Python

evaluate_reverse_polish_notation_stack.py

from typing import List


def evaluate_rpn_stack(tokens: List[str]) -> int:
    """
    Evaluate Reverse Polish Notation using a stack.

    Time: O(n) - process each token once
    Space: O(n) - stack stores operands
    """
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token in operators:
            # Pop two operands (order matters for - and /)
            b = stack.pop()
            a = stack.pop()

            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            else:  # token == '/'
                # Truncate towards zero (Python's int() does this)
                result = int(a / b)

            stack.append(result)
        else:
            # It's a number
            stack.append(int(token))

    return stack[0]


# Test cases
if __name__ == "__main__":
    print(evaluate_rpn_stack(["2", "1", "+", "3", "*"]))  # 9
    print(evaluate_rpn_stack(["4", "13", "5", "/", "+"]))  # 6
    print(evaluate_rpn_stack(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22
    print(evaluate_rpn_stack(["3", "4", "+"]))  # 7
    print(evaluate_rpn_stack(["3", "4", "*"]))  # 12

C++

evaluate_reverse_polish_notation_stack.cpp

#include <vector>
#include <stack>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;

/**
 * Evaluate Reverse Polish Notation using a stack.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - stack stores operands
 */
int evaluateRpnStack(vector<string>& tokens) {
    stack<long long> st;

    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // Pop two operands (order matters for - and /)
            long long b = st.top();
            st.pop();
            long long a = st.top();
            st.pop();

            long long result;
            if (token == "+") {
                result = a + b;
            } else if (token == "-") {
                result = a - b;
            } else if (token == "*") {
                result = a * b;
            } else {  // token == "/"
                // Truncate towards zero
                result = (long long)(a / b);
            }
            st.push(result);
        } else {
            // It's a number
            st.push(stoll(token));
        }
    }

    return (int)st.top();
}

// Test cases
int main() {
    vector<string> test1 = {"2", "1", "+", "3", "*"};
    cout << evaluateRpnStack(test1) << endl;  // 9

    vector<string> test2 = {"4", "13", "5", "/", "+"};
    cout << evaluateRpnStack(test2) << endl;  // 6

    vector<string> test3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    cout << evaluateRpnStack(test3) << endl;  // 22

    vector<string> test4 = {"3", "4", "+"};
    cout << evaluateRpnStack(test4) << endl;  // 7

    vector<string> test5 = {"3", "4", "*"};
    cout << evaluateRpnStack(test5) << endl;  // 12

    return 0;
}

Java

evaluate_reverse_polish_notation_stack.java

import java.util.*;

/**
 * Evaluate Reverse Polish Notation using a stack.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - stack stores operands
 */
public class evaluate_reverse_polish_notation_stack {

    public static int evaluateRpnStack(String[] tokens) {
        Stack<Long> stack = new Stack<>();

        for (String token : tokens) {
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                // Pop two operands (order matters for - and /)
                long b = stack.pop();
                long a = stack.pop();

                long result;
                switch (token) {
                    case "+":
                        result = a + b;
                        break;
                    case "-":
                        result = a - b;
                        break;
                    case "*":
                        result = a * b;
                        break;
                    case "/":
                        // Truncate towards zero
                        result = a / b;
                        break;
                    default:
                        result = 0;
                }
                stack.push(result);
            } else {
                // It's a number
                stack.push(Long.parseLong(token));
            }
        }

        return (int) (long) stack.peek();
    }

    // Test cases
    public static void main(String[] args) {
        System.out.println(evaluateRpnStack(new String[]{"2", "1", "+", "3", "*"})); // 9
        System.out.println(evaluateRpnStack(new String[]{"4", "13", "5", "/", "+"})); // 6
        System.out.println(evaluateRpnStack(new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})); // 22
        System.out.println(evaluateRpnStack(new String[]{"3", "4", "+"})); // 7
        System.out.println(evaluateRpnStack(new String[]{"3", "4", "*"})); // 12
    }
}

JavaScript

evaluate_reverse_polish_notation_stack.js

/**
 * Evaluate Reverse Polish Notation using a stack.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - stack stores operands
 *
 * @param {string[]} tokens - Array of tokens representing RPN expression
 * @returns {number} - Result of evaluating the RPN expression
 */
function evaluateRpnStack(tokens) {
    const stack = [];
    const operators = new Set(['+', '-', '*', '/']);

    for (const token of tokens) {
        if (operators.has(token)) {
            // Pop two operands (order matters for - and /)
            const b = stack.pop();
            const a = stack.pop();

            let result;
            switch (token) {
                case '+':
                    result = a + b;
                    break;
                case '-':
                    result = a - b;
                    break;
                case '*':
                    result = a * b;
                    break;
                case '/':
                    // Truncate towards zero
                    result = Math.trunc(a / b);
                    break;
            }
            stack.push(result);
        } else {
            // It's a number
            stack.push(parseInt(token, 10));
        }
    }

    return stack[0];
}

// Test cases
console.log(evaluateRpnStack(["2", "1", "+", "3", "*"])); // 9
console.log(evaluateRpnStack(["4", "13", "5", "/", "+"])); // 6
console.log(evaluateRpnStack(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])); // 22
console.log(evaluateRpnStack(["3", "4", "+"])); // 7
console.log(evaluateRpnStack(["3", "4", "*"])); // 12

module.exports = evaluateRpnStack;

Rust

evaluate_reverse_polish_notation_stack.rs

/**
 * Evaluate Reverse Polish Notation using a stack.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - stack stores operands
 */
pub fn evaluate_rpn_stack(tokens: Vec<String>) -> i32 {
    let mut stack: Vec<i64> = Vec::new();

    for token in tokens {
        match token.as_str() {
            "+" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a + b);
            }
            "-" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a - b);
            }
            "*" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a * b);
            }
            "/" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                // Truncate towards zero
                stack.push(a / b);
            }
            _ => {
                // It's a number
                stack.push(token.parse::<i64>().unwrap());
            }
        }
    }

    stack[0] as i32
}

// Test cases
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple_addition() {
        let tokens = vec!["3".to_string(), "4".to_string(), "+".to_string()];
        assert_eq!(evaluate_rpn_stack(tokens), 7);
    }

    #[test]
    fn test_simple_multiplication() {
        let tokens = vec!["3".to_string(), "4".to_string(), "*".to_string()];
        assert_eq!(evaluate_rpn_stack(tokens), 12);
    }

    #[test]
    fn test_complex_expression() {
        let tokens = vec![
            "2".to_string(),
            "1".to_string(),
            "+".to_string(),
            "3".to_string(),
            "*".to_string(),
        ];
        assert_eq!(evaluate_rpn_stack(tokens), 9);
    }

    #[test]
    fn test_division() {
        let tokens = vec!["4".to_string(), "13".to_string(), "5".to_string(), "/".to_string(), "+".to_string()];
        assert_eq!(evaluate_rpn_stack(tokens), 6);
    }

    #[test]
    fn test_complex_mixed() {
        let tokens = vec![
            "10".to_string(),
            "6".to_string(),
            "9".to_string(),
            "3".to_string(),
            "+".to_string(),
            "-11".to_string(),
            "*".to_string(),
            "/".to_string(),
            "*".to_string(),
            "17".to_string(),
            "+".to_string(),
            "5".to_string(),
            "+".to_string(),
        ];
        assert_eq!(evaluate_rpn_stack(tokens), 22);
    }
}

fn main() {
    let test1 = vec!["2".to_string(), "1".to_string(), "+".to_string(), "3".to_string(), "*".to_string()];
    println!("{}", evaluate_rpn_stack(test1)); // 9

    let test2 = vec!["4".to_string(), "13".to_string(), "5".to_string(), "/".to_string(), "+".to_string()];
    println!("{}", evaluate_rpn_stack(test2)); // 6
}

Go

evaluate_reverse_polish_notation_stack.go

package main

import (
  "fmt"
  "strconv"
)

/**
 * Evaluate Reverse Polish Notation using a stack.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - stack stores operands
 */
func evaluateRpnStack(tokens []string) int {
  stack := make([]int64, 0)

  for _, token := range tokens {
    switch token {
    case "+":
      b := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      a := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      stack = append(stack, a+b)

    case "-":
      b := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      a := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      stack = append(stack, a-b)

    case "*":
      b := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      a := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      stack = append(stack, a*b)

    case "/":
      b := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      a := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      stack = append(stack, a/b)

    default:
      // It's a number
      num, _ := strconv.ParseInt(token, 10, 64)
      stack = append(stack, num)
    }
  }

  return int(stack[0])
}

// Test cases
func main() {
  fmt.Println(evaluateRpnStack([]string{"2", "1", "+", "3", "*"})) // 9
  fmt.Println(evaluateRpnStack([]string{"4", "13", "5", "/", "+"})) // 6
  fmt.Println(evaluateRpnStack([]string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})) // 22
  fmt.Println(evaluateRpnStack([]string{"3", "4", "+"})) // 7
  fmt.Println(evaluateRpnStack([]string{"3", "4", "*"})) // 12
}

Approach 2: Recursive Evaluation

🎯 Interview Favourite

Process tokens from right to left. When you encounter an operand, return it. When you encounter an operator, recursively get the two operands and apply the operator.

This mirrors the stack approach but uses the call stack instead of an explicit stack.

⏱ Time O(n) Single pass through tokens 💾 Space O(n) Recursion call stack depth

Step-by-step Example

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

Processing from right to left:

1. See "+" → recursively get right operand
2. See "/" → recursively get right operand (5), left operand (13) → 13 / 5 = 2
3. Back to "+" → left operand is 4 → 4 + 2 = 6

Pseudocode

function evaluateRpnRecursive(tokens, index):
    token = tokens[index]
    index--

    if token is an operator:
        right = evaluateRpnRecursive(tokens, index)
        left = evaluateRpnRecursive(tokens, index)
        return applyOperator(left, token, right)
    else:
        return int(token)

Solution Code

Python

evaluate_reverse_polish_notation_recursive.py

from typing import List


def evaluate_rpn_recursive(tokens: List[str]) -> int:
    """
    Evaluate Reverse Polish Notation using recursion with a shared index.

    Time: O(n) - process each token once
    Space: O(n) - recursion stack depth
    """
    index = [len(tokens) - 1]  # Use list to allow modification in nested function
    operators = {'+', '-', '*', '/'}

    def helper() -> int:
        token = tokens[index[0]]
        index[0] -= 1

        if token in operators:
            # Process in reverse order for recursion (right operand first)
            b = helper()
            a = helper()

            if token == '+':
                return a + b
            elif token == '-':
                return a - b
            elif token == '*':
                return a * b
            else:  # token == '/'
                return int(a / b)
        else:
            return int(token)

    return helper()


# Test cases
if __name__ == "__main__":
    print(evaluate_rpn_recursive(["2", "1", "+", "3", "*"]))  # 9
    print(evaluate_rpn_recursive(["4", "13", "5", "/", "+"]))  # 6
    print(evaluate_rpn_recursive(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22
    print(evaluate_rpn_recursive(["3", "4", "+"]))  # 7
    print(evaluate_rpn_recursive(["3", "4", "*"]))  # 12

C++

evaluate_reverse_polish_notation_recursive.cpp

#include <vector>
#include <string>
#include <iostream>

using namespace std;

/**
 * Evaluate Reverse Polish Notation using recursion.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - recursion stack depth
 */
class Solution {
private:
    int index;
    vector<string> tokens;

    int helper() {
        string token = tokens[index--];

        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // Process in reverse order for recursion (right operand first)
            long long b = helper();
            long long a = helper();

            if (token == "+") {
                return a + b;
            } else if (token == "-") {
                return a - b;
            } else if (token == "*") {
                return a * b;
            } else {  // token == "/"
                return (long long)(a / b);
            }
        } else {
            return stoll(token);
        }
    }

public:
    int evaluateRpnRecursive(vector<string>& t) {
        tokens = t;
        index = t.size() - 1;
        return helper();
    }
};

// Test cases
int main() {
    Solution sol;

    vector<string> test1 = {"2", "1", "+", "3", "*"};
    cout << sol.evaluateRpnRecursive(test1) << endl;  // 9

    vector<string> test2 = {"4", "13", "5", "/", "+"};
    cout << sol.evaluateRpnRecursive(test2) << endl;  // 6

    vector<string> test3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    cout << sol.evaluateRpnRecursive(test3) << endl;  // 22

    vector<string> test4 = {"3", "4", "+"};
    cout << sol.evaluateRpnRecursive(test4) << endl;  // 7

    vector<string> test5 = {"3", "4", "*"};
    cout << sol.evaluateRpnRecursive(test5) << endl;  // 12

    return 0;
}

Java

evaluate_reverse_polish_notation_recursive.java

import java.util.*;

/**
 * Evaluate Reverse Polish Notation using recursion.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - recursion stack depth
 */
public class evaluate_reverse_polish_notation_recursive {

    private String[] tokens;
    private int index;

    private long helper() {
        String token = tokens[index--];

        if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
            // Process in reverse order for recursion (right operand first)
            long b = helper();
            long a = helper();

            switch (token) {
                case "+":
                    return a + b;
                case "-":
                    return a - b;
                case "*":
                    return a * b;
                case "/":
                    return a / b;
                default:
                    return 0;
            }
        } else {
            return Long.parseLong(token);
        }
    }

    public int evaluateRpnRecursive(String[] t) {
        tokens = t;
        index = t.length - 1;
        return (int) helper();
    }

    // Test cases
    public static void main(String[] args) {
        evaluate_reverse_polish_notation_recursive sol = new evaluate_reverse_polish_notation_recursive();

        System.out.println(sol.evaluateRpnRecursive(new String[]{"2", "1", "+", "3", "*"})); // 9
        System.out.println(sol.evaluateRpnRecursive(new String[]{"4", "13", "5", "/", "+"})); // 6
        System.out.println(sol.evaluateRpnRecursive(new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})); // 22
        System.out.println(sol.evaluateRpnRecursive(new String[]{"3", "4", "+"})); // 7
        System.out.println(sol.evaluateRpnRecursive(new String[]{"3", "4", "*"})); // 12
    }
}

JavaScript

evaluate_reverse_polish_notation_recursive.js

/**
 * Evaluate Reverse Polish Notation using recursion.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - recursion stack depth
 *
 * @param {string[]} tokens - Array of tokens representing RPN expression
 * @returns {number} - Result of evaluating the RPN expression
 */
function evaluateRpnRecursive(tokens) {
    let index = tokens.length - 1;
    const operators = new Set(['+', '-', '*', '/']);

    function helper() {
        const token = tokens[index--];

        if (operators.has(token)) {
            // Process in reverse order for recursion (right operand first)
            const b = helper();
            const a = helper();

            switch (token) {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    return Math.trunc(a / b);
            }
        } else {
            return parseInt(token, 10);
        }
    }

    return helper();
}

// Test cases
console.log(evaluateRpnRecursive(["2", "1", "+", "3", "*"])); // 9
console.log(evaluateRpnRecursive(["4", "13", "5", "/", "+"])); // 6
console.log(evaluateRpnRecursive(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])); // 22
console.log(evaluateRpnRecursive(["3", "4", "+"])); // 7
console.log(evaluateRpnRecursive(["3", "4", "*"])); // 12

module.exports = evaluateRpnRecursive;

Rust

evaluate_reverse_polish_notation_recursive.rs

/**
 * Evaluate Reverse Polish Notation using recursion.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - recursion stack depth
 */
pub fn evaluate_rpn_recursive(tokens: Vec<String>) -> i32 {
    let mut index = tokens.len() as i32 - 1;

    fn helper(tokens: &[String], index: &mut i32) -> i64 {
        let token = tokens[*index as usize].clone();
        *index -= 1;

        match token.as_str() {
            "+" => {
                let b = helper(tokens, index);
                let a = helper(tokens, index);
                a + b
            }
            "-" => {
                let b = helper(tokens, index);
                let a = helper(tokens, index);
                a - b
            }
            "*" => {
                let b = helper(tokens, index);
                let a = helper(tokens, index);
                a * b
            }
            "/" => {
                let b = helper(tokens, index);
                let a = helper(tokens, index);
                a / b
            }
            _ => token.parse::<i64>().unwrap(),
        }
    }

    helper(&tokens, &mut index) as i32
}

// Test cases
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple_addition() {
        let tokens = vec!["3".to_string(), "4".to_string(), "+".to_string()];
        assert_eq!(evaluate_rpn_recursive(tokens), 7);
    }

    #[test]
    fn test_simple_multiplication() {
        let tokens = vec!["3".to_string(), "4".to_string(), "*".to_string()];
        assert_eq!(evaluate_rpn_recursive(tokens), 12);
    }

    #[test]
    fn test_complex_expression() {
        let tokens = vec![
            "2".to_string(),
            "1".to_string(),
            "+".to_string(),
            "3".to_string(),
            "*".to_string(),
        ];
        assert_eq!(evaluate_rpn_recursive(tokens), 9);
    }

    #[test]
    fn test_division() {
        let tokens = vec!["4".to_string(), "13".to_string(), "5".to_string(), "/".to_string(), "+".to_string()];
        assert_eq!(evaluate_rpn_recursive(tokens), 6);
    }

    #[test]
    fn test_complex_mixed() {
        let tokens = vec![
            "10".to_string(),
            "6".to_string(),
            "9".to_string(),
            "3".to_string(),
            "+".to_string(),
            "-11".to_string(),
            "*".to_string(),
            "/".to_string(),
            "*".to_string(),
            "17".to_string(),
            "+".to_string(),
            "5".to_string(),
            "+".to_string(),
        ];
        assert_eq!(evaluate_rpn_recursive(tokens), 22);
    }
}

fn main() {
    let test1 = vec!["2".to_string(), "1".to_string(), "+".to_string(), "3".to_string(), "*".to_string()];
    println!("{}", evaluate_rpn_recursive(test1)); // 9

    let test2 = vec!["4".to_string(), "13".to_string(), "5".to_string(), "/".to_string(), "+".to_string()];
    println!("{}", evaluate_rpn_recursive(test2)); // 6
}

Go

evaluate_reverse_polish_notation_recursive.go

package main

import (
  "fmt"
  "strconv"
)

/**
 * Evaluate Reverse Polish Notation using recursion.
 *
 * Time: O(n) - process each token once
 * Space: O(n) - recursion stack depth
 */
type RPNEvaluator struct {
  tokens []string
  index  int
}

func (e *RPNEvaluator) helper() int64 {
  token := e.tokens[e.index]
  e.index--

  switch token {
  case "+":
    b := e.helper()
    a := e.helper()
    return a + b

  case "-":
    b := e.helper()
    a := e.helper()
    return a - b

  case "*":
    b := e.helper()
    a := e.helper()
    return a * b

  case "/":
    b := e.helper()
    a := e.helper()
    return a / b

  default:
    num, _ := strconv.ParseInt(token, 10, 64)
    return num
  }
}

func evaluateRpnRecursive(tokens []string) int {
  evaluator := &RPNEvaluator{
    tokens: tokens,
    index:  len(tokens) - 1,
  }
  return int(evaluator.helper())
}

// Test cases
func main() {
  fmt.Println(evaluateRpnRecursive([]string{"2", "1", "+", "3", "*"})) // 9
  fmt.Println(evaluateRpnRecursive([]string{"4", "13", "5", "/", "+"})) // 6
  fmt.Println(evaluateRpnRecursive([]string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})) // 22
  fmt.Println(evaluateRpnRecursive([]string{"3", "4", "+"})) // 7
  fmt.Println(evaluateRpnRecursive([]string{"3", "4", "*"})) // 12
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

evaluate_reverse_polish_notation_space_optimized.py

"""
Solution for Evaluate Reverse Polish Notation
"""

def solve():
    """Implementation for approach 3 of Evaluate Reverse Polish Notation"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

evaluate_reverse_polish_notation_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Evaluate Reverse Polish Notation
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

EvaluateReversePolishNotationSpaceOptimized.java

/**
 * Solution for Evaluate Reverse Polish Notation
 * Approach 3
 */
public class EvaluateReversePolishNotationSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

evaluate_reverse_polish_notation_space_optimized.js

/**
 * Solution for Evaluate Reverse Polish Notation
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

evaluate_reverse_polish_notation_space_optimized.rs

/// Solution for Evaluate Reverse Polish Notation
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

evaluate_reverse_polish_notation_space_optimized.go

package main

import "fmt"

// Solution for Evaluate Reverse Polish Notation
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Operand order: The first pop is the second operand. For 5 - 3 -, if you pop in the wrong order, you get 3 - 5 = -2 instead of 5 - 3 = 2.
• Division truncation: Most languages have different rules. Use int(a / b) in Python (truncates toward zero), and ensure C++ and Java do the same.
• Negative numbers: Tokens like "-11" are single tokens, not the operator - followed by 11. Parse carefully.
• Single operand: The input ["42"] is valid and should return 42 without any operations.

Related Problems

• Basic Calculator II ↗ Medium #227
• Basic Calculator ↗ Hard #224
• Expression Add Operators ↗ Hard #282
• Decode String ↗ Medium #394

Interview Tips

Key trade-offs to discuss

• Stack vs Recursion: Both are O(n) time and space. Stack is more common in production; recursion is more elegant for interviews if you want to demonstrate understanding of call stacks.
• Why RPN? RPN eliminates the need for parentheses and operator precedence rules. Many calculators use it internally.
• Division edge case: Clarify with the interviewer whether to truncate towards zero or use floor division. LeetCode uses truncation towards zero.
• Performance note: The stack approach avoids function call overhead, making it slightly faster in practice, though both are O(n).
• Follow-ups to anticipate:
  • “What if we wanted to support functions like sin(x) or sqrt(x)?” (Add special handling for function names)
  • “Can you convert infix to RPN?” (This is the Shunting Yard algorithm)
  • “What if operators had different precedence?” (Harder in RPN; easier in infix)

← Previous
#149 Max Points on a Line Next
#151 Reverse Words in String →