Evaluate Reverse Polish Notation

• medium
• Problem URL

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 the intermediate calculations can be represented in a 32-bit integer.

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Solution

Use a stack to store the numbers. When we encounter an operator, we pop the last two numbers from the stack, perform the operation and push the result back to the stack.

Implementation

JavaScript

function evalRPN(tokens) {
  const operators = {
    "+": (a, b) => b + a,
    "-": (a, b) => b - a,
    "/": (a, b) => (b / a) | 0,
    "*": (a, b) => b * a,
  };

  const stack = [];

  for (const token of tokens) {
    const operator = operators[token];
    if (operator) {
      const result = operator(stack.pop(), stack.pop());
      stack.push(result);
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}

TypeScript

type Operator = "+" | "-" | "*" | "/";
type OperatorFunction = (a: number, b: number) => number;

function evalRPN(tokens: string[]): number {
  const operators: {
    [key in Operator]: OperatorFunction;
  } = {
    "+": (a, b) => b + a,
    "-": (a, b) => b - a,
    "*": (a, b) => b * a,
    "/": (a, b) => (b / a) | 0,
  };

  const stack: number[] = [];

  for (const token of tokens) {
    const operator: OperatorFunction | undefined = operators[token];
    if (operator) {
      const result = operator(stack.pop()!, stack.pop()!);
      stack.push(result);
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}

Go

func evalRPN(tokens []string) int {
  var operations = map[string]func(int, int) int{
    "+": func(a, b int) int { return a + b },
    "-": func(a, b int) int { return a - b },
    "*": func(a, b int) int { return a * b },
    "/": func(a, b int) int { return a / b },
  }

  stack := make([]int, 0)

  for _, token := range tokens {
    if operation, isOperator := operations[token]; isOperator {
      operand2 := stack[len(stack)-1]
      operand1 := stack[len(stack)-2]
      stack = stack[:len(stack)-2]

      result := operation(operand1, operand2)
      stack = append(stack, result)
    } else {
      number, err := strconv.Atoi(token)
      if err != nil {
        panic("Invalid operand")
      }
      stack = append(stack, number)
    }
  }
  return stack[0]
}

Python

class Solution:
    def add(self, a: int, b: int):
        return a + b

    def sub(self, a: int, b: int):
        return a - b

    def mul(self, a: int, b: int):
        return a * b

    def div(self, a: int, b: int):
        return int(a / b)

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operations = {
            "+": self.add,
            "-": self.sub,
            "*": self.mul,
            "/": self.div,
        }

        for token in tokens:
            if token in operations:
                op = operations[token]
                right = stack.pop()
                left = stack.pop()
                result = op(left, right)
                stack.append(result)
            else:
                stack.append(int(token))
        return stack.pop()

C++

#include <stack>
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> my_stack;
        for (string& token : tokens) {
            if (token == "+" || token == "-" || token == "/" || token == "*") {
                int second = my_stack.top();
                my_stack.pop();
                int first = my_stack.top();
                my_stack.pop();
                int result = 0;

                // token[0] converts string to char
                switch (token[0]) {
                case '+':
                    result = first + second;
                    break;

                case '-':
                    result = first - second;
                    break;

                case '*':
                    result = first * second;
                    break;

                case '/':
                    result = first / second;
                    break;

                default:
                    throw std::invalid_argument("Invalid operator");
                }
                my_stack.push(result);
            } else {
                my_stack.push(std::stoi(token));
            }
        }
        return my_stack.top();
    }
};

Pseudocode

1. Create a map of operators to their functions.
2. Create a stack.
3. Iterate over the tokens.
   • If the token is an operator, pop the last two numbers from the stack, perform the operation and push the result back to the stack.
   • Otherwise, push the number to the stack.
4. Return the last number from the stack.

Complexity Analysis

• The time complexity is O(n) because we iterate over all the tokens.
• The space complexity is O(n) because we use a stack to store the numbers.