计算器(二)——加减和乘除

LeetCode_227_BasicCalculatorII

题目分析：

没有了括号，但是有加减和乘除间的优先级。
同样可以用栈。但是由于加减和乘除只有'一层'嵌套，所以栈最多被压一层，那么也可以用变量来替换栈。

解法一：栈

public static int calculate(String s) {
    int res = 0, num = 0, n = s.length();
    char op = '+';
    Stack<Integer> st = new Stack<>();
    for (int i = 0; i < n; ++i) {
        char c = s.charAt(i);
        if (c >= '0') {
            num = num * 10 + c - '0';
        }
        if ((c < '0' && c != ' ') || i == n - 1) {
            if (op == '+') st.push(num);
            if (op == '-') st.push(-num);
            if (op == '*' || op == '/') {
                int tmp = (op == '*') ? st.pop() * num : st.pop() / num;
                st.push(tmp);
            }
            op = c;
            num = 0;
        }
    }
    while (!st.empty()) {
        res += st.pop();
    }
    return res;
}

解法二：变量替换栈

/**
 * 只有加减乘除优先级
 * 其实本质就是------------有且仅有一层括号，不会出现括号嵌套
 * 那么用栈就没有必要了，用一个变量curRes代替栈的功能即可,毕竟用栈只需要一层栈。
 * 妙不可言
 */
public static int calculate(String s) {
    int res = 0, curRes = 0, num = 0, n = s.length();
    char op = '+';
    for (int i = 0; i < n; ++i) {
        char c = s.charAt(i);
        if (c >= '0') {
            num = num * 10 + c - '0';
        }
        if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
            switch (op) {
                case '+': curRes += num; break;
                case '-': curRes -= num; break;
                case '*': curRes *= num; break;
                case '/': curRes /= num; break;
            }
            if (c == '+' || c == '-' || i == n - 1) {
                res += curRes;
                curRes = 0;
            }
            op = c;
            num = 0;
        }
    }
    return res;
}