LeetCode227 基本计算器II

链接： https://leetcode-cn.com/problems/basic-calculator-ii/

题意

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。表达式仅包含加减乘除，且不涉及负数运算

解法

表达式计算属于经典的问题了
我只能想到的是中缀表达式转后缀表达式，再进行计算
于是又去复习了一下中缀转后缀的做法，核心步骤如下:
利用两个栈S1，S2: 其中S1存放操作符，S2存放操作数

从左往右遍历中缀表达式，如果遇到数字，则放入S2中，如果遇到操作符，则放入S1中。在放操作符的时候有一定的规则，如果栈为空或栈顶元素为（，则直接压栈。如果是(，也直接压栈;如果栈顶元素为普通操作符，则比较优先级，如果待压栈的操作符比栈顶操作符优先级高，则直接压栈，否则将S1中的栈顶元素出栈，并压入S2中，再接着比较S1栈顶元素的优先级。如果遇到)，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃。最后将S1中剩余的运算符依次弹出并压入S2，逆序输出S2（从栈底到栈顶）便得到了后缀表达式。（注意：等号的优先级最低，因为要到最后才进行赋值操作）

得到后缀表达式之后，计算就变得方便多了，遇到数字就压栈，遇到操作符的时候，pop出栈顶的两个元素，进行计算后将结果又压入栈中，这样一直下去，直到得到最终结果。

按照这个思路，写了很长的快100行的代码，发现速度和空间使用都不尽如人意

翻了一下题解发现了一种只需要使用一个栈的做法。
由于表达式中不含小数括号和负数，所以可以保存所有计算中产生的中间结果，并把它们全加起来，就可以得到结果
中间遇到乘号或除号，可以将上个数pop，并与当前的数值进行计算，并将计算出来的结果压栈
巧妙的地方是每次保存上一个运算符号，这样就可以完成中缀表达式的计算（即进行的是上一次的运算）

另外还有种相似的解法，在字符串的最左边加上一个+号，从左向右处理，每次根据不同的运算符进行不同的运算，最后得到两个数字相加的结果

代码

解法一

class Solution {
public:
    int calculate(string s) {
        vector<int> digits;
        int d = 0, ans = 0;
        int len = s.size();
        char op = '+';
        for (int i = 0; i < len; i++) {
            if (s[i] == ' ' && i < len - 1) continue;
            if (isdigit(s[i])) {
                d = d * 10 + (s[i] - '0');
            }
            if (!isdigit(s[i]) || i == len - 1) {
                if (op == '+') {
                    digits.push_back(d);
                }
                else if (op == '-') {
                    digits.push_back(-d);
                }
                else if (op == '*') {
                    int t = digits.back();
                    digits.pop_back();
                    digits.push_back(t * d);
                }
                else {
                    int t = digits.back();
                    digits.pop_back();
                    digits.push_back(t / d);
                }
                op = s[i];
                d = 0;
            }
        }
        for ( ;digits.size(); digits.pop_back()) {
            // cout << digits.back() << endl;
            ans += digits.back();
        }
        return ans;
    }
};

解法二

class Solution {
public:
    int parseNum(string& s, int& i) {
        int ret = 0;
        while(i < s.length() && isdigit(s[i])) {
            ret = ret * 10 - '0' + s[i];
            i++;
        }
        return ret;
    }
    int calculate(string s) {
        vector<int> digits;
        int len = s.size();
        int left = 0, right = 0, i = 0;
        char op = '+';
        while(i < len) {
            if (s[i] != ' ') {
                int n = parseNum(s, i);
                switch (op)
                {
                    case '+': left += right; right = n; break;
                    case '-':left += right; right = -n; break;
                    case '*': right *= n; break;
                    case '/': right /= n; break;
                    default: break;
                }
                if (i < len) {
                    op = s[i];
                }
            }
            i++;
        }
        return left + right;
    }
};