Question

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

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1:

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

Example 2:

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

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"] Output: 22 Explanation: ((10 (6 / ((9 + 3) -11))) + 17) + 5 = ((10 (6 / (12 -11))) + 17) + 5 = ((10 (6 / -132)) + 17) + 5 = ((10 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

Difficulty:Medium

Category:Stack

Analyze

Solution

class Solution {
 public:
  int evalRPN(vector<string>& tokens) {
    stack<string> sta;
    for (auto token : tokens) {
      // If this is a number, then push it to the stack.
      if (!is_operator(token)) {
        sta.push(token);
      } else {
        int b = stoi(sta.top());
        sta.pop();
        int a = stoi(sta.top());
        sta.pop();
        if (token == "+")
          a += b;
        else if (token == "-")
          a -= b;
        else if (token == "*")
          a *= b;
        else
          a /= b;
        sta.push(to_string(a));
      }
    }
    return stoi(sta.top());
  }

  bool is_operator(const string& token) {
    return token.size() == 1 && string("+-*/").find(token) != string::npos; }
};