题目描述

给定一个化学式 formula（作为字符串），返回每种原子的数量。

原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。

两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。

一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

样例

输入: 
formula = "H2O"
输出: "H2O"
解释: 
原子的数量是 {'H': 2, 'O': 1}。

输入: 
formula = "Mg(OH)2"
输出: "H2MgO2"
解释: 
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。

输入: 
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释: 
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

提示

• 所有原子的第一个字母为大写，剩余字母都是小写。
• formula 的长度在 [1, 1000] 之间。
• formula 只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。

算法

(栈) $O(n \log n)$

1. 不妨假设每个原子出现的次数不超过 32 位有符号整型的范围。
2. 维护一个栈，栈中存放二元组，表示原子的名称和原子的数量。
3. 扫描原分子式，如果遇到一个原子，则取出名称和其对应的数量。如果遇到左括号，则左括号进栈。
4. 如果遇到右括号，首先取出括号后数值，然后栈顶出栈直到遇到左括号。出栈后的二元组需要将对应位置上的值乘上括号后的数值，然后再次进栈。
5. 最后需要将栈中所有原子出栈，并统计每个原子的出现次数，然后排序输出。

时间复杂度

• 维护栈时，每个位置仅被遍历常数次。
• 排序需要 $O(n \log n)$ 的时间，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储栈和其他辅助数组。

C++ 代码

class Solution {
public:
    int get_num(const string &s, int &i) {
        int n = s.length();
        if (i == n || !(s[i] >= '0' && s[i] <= '9'))
            return 1;

        int cnt = 0;
        while (i < n && s[i] >= '0' && s[i] <= '9') {
            cnt = cnt * 10 + s[i] - '0';
            i++;
        }

        return cnt;
    }

    string get_token(const string &s, int &i) {
        int n = s.length();
        string token;
        token += s[i++];

        while (i < n && s[i] >= 'a' && s[i] <= 'z') {
            token += s[i];
            i++;
        }

        return token;
    }

    string countOfAtoms(string formula) {
        stack<pair<string, int>> st;
        int n = formula.length();

        int i = 0;
        while (i < n) {
            if (formula[i] == '(') {
                i++;
                st.push(make_pair("(", -1));
            } else if (formula[i] == ')') {
                i++;
                int cnt = get_num(formula, i);

                vector<pair<string, int>> tmp;
                while (st.top().first != "(") {
                    tmp.emplace_back(st.top().first, st.top().second * cnt);
                    st.pop();
                }
                st.pop();

                for (const auto &t : tmp)
                    st.push(t);
            } else {
                string name(get_token(formula, i));
                int cnt = get_num(formula, i);
                st.push(make_pair(name, cnt));
            }
        }

        unordered_map<string, int> h;
        while (!st.empty()) {
            h[st.top().first] += st.top().second;
            st.pop();
        }

        vector<pair<string, int>> res(h.begin(), h.end());
        sort(res.begin(), res.end());
        string ans;

        for (const auto &at : res) {
            ans += at.first;
            if (at.second > 1)
                ans += to_string(at.second);
        }

        return ans;
    }
};