algorithm/Algorithm/cpp/0772.BasicCalculatorIII/calculate.cpp at master · wuvei/algorithm · 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
class Solution {
public:
    /**
     * @param s: the expression string
     * @return: the answer
     */
    using ll = long long;

    inline void calc() {
        ll n1 = vals.top();
        vals.pop();
        ll n2 = vals.top();
        vals.pop();
        char op = ops.top();
        ops.pop();
        switch(op) {
            case '+':
                vals.push(n1 + n2);
                break;
            case '-':
                vals.push(n2 - n1);
                break;
            case '*':
                vals.push(n1 * n2);
                break;
            case '/':
                vals.push(n2 / n1);
                break;
        }
    }
    int calculate(string &s) {
        stack<ll>().swap(vals);
        stack<char>().swap(ops);
        string num;
        for (char c: s) {
            if (std::isdigit(c)) num += c;
            else {
                if (num != "") vals.push(std::stoll(num));
                num = "";
                if (c == ' ') continue;
                if (c == '(') ops.push(c);
                else if (c == ')') {
                    while (!ops.empty() && ops.top() != '(') {
                        calc();
                    }
                    ops.pop();
                }
                else { // op = +,-,*,/
                    while (!ops.empty() && ops.top() != '(' && priority[c] >= priority[ops.top()] ) {
                        calc();
                    }
                    ops.push(c);
                }
            }
        }
        if (num != "") vals.push(std::stoll(num));
        while (!ops.empty()) {
            calc();
        }
        return int(vals.top());
    }
private:
    stack<ll> vals;
    stack<char> ops;
    unordered_map<char, int> priority = {{'+', 2}, {'-', 2}, {'*', 1}, {'/', 1}};
};