LeetCode – Evaluate Reverse Polish Notation

题目：

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

解题：

          逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），将操作数放到操作符前的一种数学表达式方式，也被称作后缀表示法。

         1. 使用栈： 针对本题由于操作符指定为二元运算，具体操作有流程有所简化， 遇到操作数入栈， 遇到操作符，将两个操作数出栈，进行运算，将结果再次入栈，以此类推，知道完成所有数组的遍历，栈顶指针即为结果。

实现：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> ss;
        if (tokens.size() == 1) { 
            return stoi(tokens[0]);
        } 
        for (auto s:tokens){            
            if (s !="+" && s !="-" && s!="*" && s!="/" ){
                ss.push(stoi(s));
            }
            else{
                int num2 = ss.top();
                ss.pop();
                int num1 = ss.top();
                ss.pop();
                
                int result;
                switch (s[0]){
                    case '+':
                        result = num1+num2;
                        break;
                    case '-':
                        result = num1-num2;
                        break;
                    case '*':
                        result = num1*num2;
                        break;
                    case '/':
                        if (num2 == 0){
                            result = 0;
                        }else {
                            result = num1/num2;
                        }
                        break;
                    default:
                        result = 0;
                        break;
                }
               
                ss.push(result);
            }
        }
             
        return ss.top();
    }
};

             2. 递归： 从数组末尾开始调用，如果遇到操作符，继续向前递归调用，找到对应的两个数字后，进行运算返回结果； 如果遇到数字，直接返回。

实现：

int evalRPN(vector<string>& tokens) {
    auto t = tokens.back(); tokens.pop_back();
    if (isdigit(t.back())) return stoi(t);
    int n2 = evalRPN(tokens), n1 = evalRPN(tokens);
    return t[0] == '+' ? n1 + n2 : t[0] == '-' ? n1 - n2 : t[0] == '*' ? n1 * n2 : n1 / n2;
}

参考：

[LeetCode] Evaluate Reverse Polish Notation 计算逆波兰表达式