Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

150. Evaluate Reverse Polish Notation

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  int evalRPN(vector<string>& tokens) {
    stack<int> stack;
    const unordered_map<string, function<int(int, int)>> op{
        {"+", plus<int>()},
        {"-", minus<int>()},
        {"*", multiplies<int>()},
        {"/", divides<int>()}};

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

    return stack.top();
  }
};




			


class Solution {
  public int evalRPN(String[] tokens) {
    Deque<Integer> 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 int b = stack.pop();
          final int a = stack.pop();
          stack.push(a / b);
          break;
        default:
          stack.push(Integer.parseInt(token));
      }

    return stack.peek();
  }
}




			


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]