Mind palace

some thoughts

0%

772. Basic Calculator III

Posted on Edited on In Disqus:
Symbols count in article: 5k Reading time ≈ 5 mins.

O(n) time
通用解法

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
class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) { // 用函数调用来模拟栈操作，这里i必须是引用
        char op = '+';
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
            } else if (c != ' ') { // +-*/)五种操作符都要运行
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || c == ')') { // 只要不是*/都要对前面进行一次累加操作
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
                if (c == ')') break;
            }
        }
        return res;
    }
};
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
class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) { // 用函数调用来模拟栈操作，这里i必须是引用
        char op = '+';
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (; i < n && op != ')'; ++i) { // 结束条件是op != ')'而不是c != ')'因为即便c是')'也需要用op来进行一步操作
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
                --i; // 因为当op是')'才返回，这时i已经指向了')'的下一个，所以要回退一个
            } else if (c != ' ') { // +-*/)五种操作符都要运行
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || c == ')') { // 只要不是*/都要对前面进行一次累加操作
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

recursive
worst case O(n2) time
1-2*3 ==> 0+1+-2*3+
遇到左括号找对应的右括号递归处理

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
class Solution {
public:
    int calculate(string s) {
        char op = '+';
        s += "+"; // 补一个+方便操作
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break; // 括号匹配
                }
                num = calculate(s.substr(j + 1, i - j - 1));
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                switch (op) { // 这个op不是当前的，是之前的，即curRes op num c
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-') {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

stack O(n) time O(n) space

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
    int calculate(string s) {
        s.erase(remove_if(s.begin(), s.end(), [](char c) {return c == ' ';}), s.end()); // 先去掉多余的空格
        s = "(" + s + ")";
        double x = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            switch (s[i]) {
                case '+': {
                    if (i > 0 && !isdigit(s[i - 1]) && s[i - 1] != ')') {
                        continue;
                    }
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    if (!optr.empty() && optr.back() != '(') {
                        eval();
                    }
                    optr.push_back('+');
                }
                    break;
                case '-': {
                    if (i == 0 || s[i - 1] == '(') {
                        optr.push_back('*');
                        opnd.push_back(-1);
                    } else if (s[i - 1] == '+') {
                        optr.back() = '-';
                    } else if (s[i - 1] == '-') {
                        optr.back() = '+';
                    } else if (s[i - 1] == '*' || s[i - 1] == '/') {
                        opnd.back() *= -1;
                    } else if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                        if (!optr.empty() && optr.back() != '(') {
                            eval();
                        }
                        optr.push_back('-');
                    } else {
                        if (!optr.empty() && optr.back() != '(') {
                            eval();
                        }
                        optr.push_back('-');
                    }
                }
                    break;
                case '*':
                case '/': {
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    if (!optr.empty() && (optr.back() == '*' || optr.back() == '/')) {
                        eval();
                    }
                    optr.push_back(s[i]);
                }
                    break;
                case '(': {
                    optr.push_back('(');
                }
                    break;
                case ')': {
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    while (optr.back() != '(') {
                        eval();
                    }
                    optr.pop_back();
                }
                    break;
                default: {
                    x = x * 10 + s[i] - '0';
                }
                    break;
            }
        }
        return opnd.back();
    }

    void eval() {
        char op = optr.back(); optr.pop_back();
        auto b = opnd.back(); opnd.pop_back();
        auto a = opnd.back(); opnd.pop_back();
        switch (op) {
            case '+': opnd.push_back(a + b); break;
            case '-': opnd.push_back(a - b); break;
            case '*': opnd.push_back(a * b); break;
            case '/': opnd.push_back(floor((double)a / b)); break;
        }
    }

    vector<char> optr;
    vector<double> opnd;
};