栈实现计算器

leetcode 224 使用栈实现计算器。
扩展一下，不仅仅是加减，乘除也是可以的。
另外对可以实现负数(-2) + 3这种负数的运算。

双栈
opv: 数字栈
opc: 符号栈

优先级的话 :

1. 如果栈顶是加减，当前是加减，就可以计算。
2. 如果栈顶是乘除，当前不是左括号，就可以计算。
3. 如果栈顶是左括号，当前如果是右括号，就直接出栈一次, 否则不计算。

对于负数的处理：
负数前面没有数字，也没有右括号，所以满足这两个特征的就是负数。

对数字的处理:
数字注意中间计算的时候使用long进行强转。否则如果是INT_MAX会爆int。

对左右括号的处理:
右括号不入栈。左括号不计算。

对空格的处理：
只清空数字计数器cur, 不进行计算。

class Solution {
public:

    int calculate(string s) {
        stack<int>opv;
        stack<char>opc;
        auto cal = [&]() {
            char ch = opc.top(); opc.pop();
            int a = opv.top(); opv.pop();
            int b = opv.top(); opv.pop();
            if (ch == '+') opv.push(b + a);
            else if (ch == '-') opv.push(b - a);
            else if (ch == '*') opv.push(b * a);
            else if (ch == '/') opv.push(b / a);
            // printf("%d %c %d = %d\n", b, ch, a, opv.top());
        };
        auto check = [&](char ch) -> int {
            char top = opc.top();
            if (top == '+' || top == '-') {
                if (ch == '+' || ch == '-' || ch == ')') 
                    return 1;
            }
            else if (top == '*' || top == '/') {
                if (ch != '(')
                    return 1;
            }
            else if (top == '(' && ch == ')') return 0; 
            return -1;
        };
        s += ' ';
        int cur = -1;
        opc.push('#');
        char pre = '#';
        for (char ch : s) {
            if (isdigit(ch)) {
                if (cur == -1) cur = 0;
                cur = (long)cur * 10 + ch - '0';            // 2. 防止爆int
                // printf("%d\n", cur);
            }
            else {
                if (cur != -1) opv.push(cur);               
                cur = -1;
                if (ch == ' ') continue;                    // 空格
                if (ch == '-' && (!isdigit(pre) && pre != ')')) { // 负数
                    // printf("pre = %c\n", pre);
                    opv.push(0);
                }
                while (check(ch) > 0) cal();
                if (check(ch) == 0)  // 右括号，左括号出来一个，不全部出来
                    opc.pop();
                if (ch != ')')             // 右括号不放进去
                    opc.push(ch);
            }
            if (pre != ' ') pre = ch;
        }
        while (opc.top() != '#') cal();
        return opv.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59