Leetcode.150.Evaluate Reverse Po

题目

给定一个字符数组, 求运算结果.

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

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

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

思路

由于没有括号, 此题比较简单.
栈, 遇到数字就压栈, 遇到标点就运算.

bool isOperator(string str) {
    if (str == "+" || str == "-" ||
        str == "*" || str == "/" ) {
        return true;
    }
    return false;
}

int doOperator(int a, int b, string op) {
    if (op == "+") {
        return a+b;
    } else if (op == "-") {
        return a-b;
    } else if (op == "*") {
        return a*b;
    } else if (op == "/") {
        return a/b;
    }
    return 0;
}

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for(string str : tokens) {
        if (isOperator(str)) {
            int b = s.top();
            s.pop();
            int a = s.top();
            s.pop();
            int res = doOperator(a, b, str);
            s.push(res);
        } else {
            int val = stoi(str);
            s.push(val);
        }
    }
    return s.top();
}

总结

熟练掌握栈和队列的使用场景.