LeetCode/leetcode/224. Basic Calculator/s1.cpp at master · TheCodingBlogs/LeetCode · GitHub

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
// OJ: https://leetcode.com/problems/basic-calculator/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    vector<string> tokenize(string &s) {
        vector<string> ans;
        for (int i = 0, N = s.size(); i < N; ) {
            while (i < N && s[i] == ' ') ++i;
            if (i >= N) break;
            if (isdigit(s[i])) {
                int j = i;
                while (i < N && isdigit(s[i])) ++i;
                ans.push_back(s.substr(j, i - j));
            } else ans.push_back(s.substr(i++, 1));
        }
        return ans;
    }
    vector<string> toRpn(vector<string> tokens) {
        vector<string> ans;
        stack<string> ops;
        for (auto &s : tokens) {
            switch (s[0]) {
                case '(': ops.push(s); break;
                case ')':
                    while (ops.top() != "(") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.pop();
                    break;
                case '+':
                case '-':
                    if (ops.size() && (ops.top() == "+" || ops.top() == "-")) {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.push(s);
                    break;
                default: ans.push_back(s); break;
            }
        }
        while (ops.size()) {
            ans.push_back(ops.top());
            ops.pop();
        }
        return ans;
    }
    int calc(vector<string> rpn) {
        stack<int> s;
        for (auto &t : rpn) {
            switch (t[0]) {
                case '+':
                case '-': {
                    int b = s.top();
                    s.pop();
                    s.top() += t == "+" ? b : -b;
                    break;
                }
                default: s.push(stoi(t)); break;
            }
        }
        return s.top();
    }
public:
    int calculate(string s) {
        return calc(toRpn(tokenize(s)));
    }
};