# 726. Number of Atoms

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

实现参考了花花的[讲解](https://www.youtube.com/watch?v=6nQ2jfs7a7I)。

```
/*
 * @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


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/stack/nested/726.-number-of-atoms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.