Skip to content

150. Evaluate Reverse Polish Notation 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int evalRPN(vector<string>& tokens) {
    stack<long> stack;
    const unordered_map<string, function<long(long, long)>> op{
        {"+", plus<long>()},
        {"-", minus<long>()},
        {"*", multiplies<long>()},
        {"/", divides<long>()}};

    for (const string& token : tokens)
      if (op.count(token)) {
        const long b = stack.top();
        stack.pop();
        const long a = stack.top();
        stack.pop();
        stack.push(op.at(token)(a, b));
      } else {
        stack.push(stoi(token));
      }

    return stack.top();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int evalRPN(String[] tokens) {
    Deque<Long> stack = new ArrayDeque<>();

    for (final String token : tokens)
      switch (token) {
        case "+":
          stack.push(stack.pop() + stack.pop());
          break;
        case "-":
          stack.push(-stack.pop() + stack.pop());
          break;
        case "*":
          stack.push(stack.pop() * stack.pop());
          break;
        case "/":
          final long b = stack.pop();
          final long a = stack.pop();
          stack.push(a / b);
          break;
        default:
          stack.push(Long.parseLong(token));
      }

    return stack.peek().intValue();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def evalRPN(self, tokens: List[str]) -> int:
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }

    for token in tokens:
      if token in operators:
        b = stack.pop()
        a = stack.pop()
        stack.append(operators[token](a, b))
      else:
        stack.append(int(token))

    return stack[0]