Basic Calculator II

解题思路

  1. 我是用双栈 AC 了这道题目，用栈来解决要注意一点：计算顺序必须从左至右，也就是当前 op 优先级小于等于栈顶时，都需要出栈计算。

  2. 最优解法是看了 Discuss 里的，我觉得很难想到，不过思维过程可以推导下，就是必须深刻理解题目给的条件和特征，想明白其实是个从左至右计算的过程，所以整个过程只需要保存一个遍历至当前的最终解和正在计算还未合入最终解的中间解。

代码

// Use Stack
class Solution {
public:
    int calculate(string s) {
        stack<int> nums;
        stack<char> ops;
        int currNum = 0;
        bool findNum = false;
        for (auto ch : s) {
            if (ch >= '0' && ch <= '9') {
                findNum = true;
                currNum = currNum * 10 + (ch - '0');
                continue;
            } else if (findNum) {
                nums.push(currNum);
                findNum = false;
                currNum = 0;
            } 
            if (ch == '*' || ch == '/') {
                if (!ops.empty() && (ops.top() == '*' || ops.top() == '/')) {
                    singleCal(nums, ops);
                }
            } else if (ch == '+' || ch == '-') {
                while (!ops.empty()) {
                    singleCal(nums, ops);
                }
            }
            if (ch != ' ') {
                ops.push(ch);
            }
        }
        if (findNum) {
            nums.push(currNum);
        }
        while (!ops.empty()) {
            singleCal(nums, ops);
        }
        return nums.empty()?0:nums.top();
    }
    
    void singleCal(stack<int>& nums, stack<char>& ops) {
        char op = ops.top();
        ops.pop();
        int num2 = nums.top();
        nums.pop();
        int num1 = nums.top();
        nums.pop();
        int res = 0;
        switch (op) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num1 - num2;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num1 / num2;
                break;
        }
        nums.push(res);
    }
};

class Solution {
public:
    int calculate(string s) {
        if (s.empty()) {
            return 0;
        }
        char op = '+';
        int res = 0;
        int currRes = 0;
        int num = 0;
        for (size_t i = 0; i < s.size(); ++i) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i] - '0');
            }
            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size()-1) {
                switch (op) {
                    case '+': currRes += num; break;
                    case '-': currRes -= num; break;
                    case '*': currRes *= num; break;
                    case '/': currRes /= num; break;
                }
                if (s[i] == '+' || s[i] == '-' || i == s.size()-1) {
                    res += currRes;
                    currRes = 0;
                }
                num = 0;
                op  = s[i];
            }
        }
        return res;
    }
};