计算器

发表于 更新于 本文字数： 316 阅读时长 ≈ 1 分钟

功能说明

  • 实现+、-、*、/、括号的整数运算
  • 实现处理多余空格

实现1（更高效）

  • 用引用l指针的方式逐步处理
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
int core(string& s, int& l) {
    stack<int> stk;
    int n = s.size();
    int num = 0;
    char sign = '+';
    for (; l < n; ++l) {
        char c = s[l];
        if (isdigit(c)) 
            num = num * 10 + (c - '0');
        // if(c == ' ') continue是不对的，因为l=n-1时一定要最后来一次
        if ((!isdigit(c) && c != ' ') || l == n - 1) {
            if (c == '(') 
                num = core(s, ++l); // 理解这种递归思想很重要
            int prev;
            switch (sign) {
            case '+':
                stk.push(num); break;
            case '-':
                stk.push(-num); break;
            case '*':
                prev = stk.top(); stk.pop();
                stk.push(prev * num);
                break;
            case '/':
                prev = stk.top(); stk.pop();
                stk.push(prev / num);
                break;
            default: break;
            }
            sign = c;
            num = 0;
            if (c == ')') 
                break;
        }
    }
    int ret = 0;
    while (!stk.empty()) {
        ret += stk.top();
        stk.pop();
    }
    return ret;
}

int caculator(string s) {
    int tmp = 0;
    return core(s, tmp);
}

实现2（更优雅）

  • 由于需要不停pop首部，所以采用deque代替移动的l，更优雅
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
int core(deque<char>& s) {
    stack<int> stk;
    int num = 0;
    char sign = '+';
    while (!s.empty()) {
        char c = s[0]; s.pop_front();
        if (isdigit(c))
            num = num * 10 + (c - '0');
        if ((!isdigit(c) && c != ' ') || s.empty()) {
            if (c == '(')
                num = core(s);
            int prev;
            switch (sign) {
            case '+':
                stk.push(num); break;
            case '-':
                stk.push(-num); break;
            case '*':
                prev = stk.top(); stk.pop();
                stk.push(prev * num);
                break;
            case '/':
                prev = stk.top(); stk.pop();
                stk.push(prev / num);
                break;
            default: break;
            }
            sign = c;
            num = 0;
            if (c == ')')
                break;
        }
    }
    int ret = 0;
    while (!stk.empty()) {
        ret += stk.top();
        stk.pop();
    }
    return ret;
}

int caculator(string s) {
    deque<char> dq;
    for (auto& e : s) dq.push_back(e);
    return core(dq);
}

参考

  • labuladong的算法小抄