726. Number of Atoms

https://leetcode.com/problems/number-of-atoms/

根据化合物的化学式统计每个原子出现的次数并按照字母序输出。和其它nested括号问题一致，括号内是个子问题，可以递归或stack做。括号后面紧跟着的数字代表子问题里头每个原子出现次数的倍数。实现两个子函数atom()和count()，分别获取当前位开始的原子和数字，调用它们能使逻辑更清晰。维持一个global的pos表示当前访问到的位置。

实现参考了花花的讲解。

/*
 * @lc app=leetcode id=726 lang=cpp
 *
 * [726] Number of Atoms
 */

// @lc code=start
class Solution {
public:
    string atom(string s, int &pos) {
        string res;
        while (isalpha(s[pos])) {
            if (res.empty() || islower(s[pos])) res += s[pos++];
            else break;
        }
        return res;
    }
    int count(string s, int &pos) {
        int num = 0;
        while (isdigit(s[pos])) {
            num = num * 10 + (s[pos++] - '0');
        }
        return num > 0 ? num : 1;
    }
    map<string, int> dfs(string s, int &pos) {
        map<string, int> freq;
        while (pos < s.length()) {
            const auto c = s[pos];
            if (c == '(') {
                const auto r = dfs(s, ++pos);
                const auto num = count(s, pos);
                for (const auto p : r) {
                    const auto i = p.first;
                    if (!freq.count(i)) freq[i] = 0;
                    freq[i] += p.second * num;
                } 
            } else if (c == ')') {
                ++pos;
                break;
            } else {
                const auto a = atom(s, pos);
                const auto num = count(s, pos);
                if (!freq.count(a)) freq[a] = 0;
                freq[a] += num;
            }
        }
        return freq;
    }

    string countOfAtoms(string formula) {
        int pos = 0;
        const auto freq = dfs(formula, pos);
        string res;
        for (const auto p : freq) {
            res += p.first;
            if (p.second > 1) res += to_string(p.second);
        }
        return res;
    }
};
// @lc code=end