LeetCode 726. Number of Atoms

Posted on Edited on In 
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
class Solution {
public:
    string countOfAtoms(string formula) {
        int i = 0, n = formula.length();
        auto parseAtom = [&]() -> string {
            string atom;
            atom += formula[i++];
            while (i < n && islower(formula[i]))
                atom += formula[i++];
            return atom;
        };
        auto parseNum = [&]() -> int {
            if (i == n || !isdigit(formula[i]))
                return 1;
            int num = 0;
            while (i < n && isdigit(formula[i]))
                num = num * 10 + (formula[i++] - '0');
            return num;
        };
        stack<unordered_map<string, int>> stk;
        stk.push({});
        while (i < n) {
            char ch = formula[i];
            if (ch == '(') {
                i++;
                stk.push({});
            } else if (ch == ')') {
                ++i;
                int num = parseNum();
                auto atomNum = stk.top();
                stk.pop();
                for (auto &[atom, v] : atomNum)
                    stk.top()[atom] += v * num;
            } else {
                string atom = parseAtom();
                int num = parseNum();
                stk.top()[atom] += num;
            }
        }
        auto &atomNum = stk.top();
        vector<pair<string, int>> pairs;
        for (auto &[atom, v] : atomNum)
            pairs.emplace_back(atom, v);
        sort(pairs.begin(), pairs.end());
        string ans;
        for (auto & [atom, num] : pairs) {
            ans += atom;
            if (num > 1)
                ans += to_string(num);
        }
        return ans;
    }
};
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
class Solution {
public:
    map<string, int> dfs(const string &formula, int &curr) {
        map<string, int> ans;
        while (curr < formula.size() && formula[curr] != ')') {
            if (formula[curr] == '(') {
                ++curr;
                auto tmp = dfs(formula, curr);
                int next = curr;
                while (next < formula.size() && isdigit(formula[next])) ++next;
                int num = curr == next ? 1 : stoi(formula.substr(curr, next - curr));
                curr = next;
                for (auto &[atom, v] : tmp)
                    ans[atom] += num * v;
            } else {
                int next = curr + 1;
                while (next < formula.size() && islower(formula[next])) ++next;
                string atom = formula.substr(curr, next - curr);
                curr = next;
                while (next < formula.size() && isdigit(formula[next])) ++next;
                int num = curr == next ? 1 : stoi(formula.substr(curr, next - curr));
                ans[atom] += num;
                curr = next;
            }
        }
        ++curr;
        return ans;
    }
    string countOfAtoms(string formula) {
        int curr = 0;
        auto atomNum = dfs(formula, curr);
        string ans;
        for (auto &[atom, num] : atomNum)
            ans += (num == 1 ? atom : atom + to_string(num));
        return ans;
    }
};