[C++] 100.00% map and stack
\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string, int> mp;\n        int carry = 1, n = formula.size(), count = 1; // c
```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string, int> mp;\n        int carry = 1, n = formula.size(), count = 1; // count is the current number of atom, for example, "(H2)2", the carry of H is 2, and the count of H is 4;\n        string cur = "", res = "";\n        bool flag = false; // to deal with situation that has two or more consecutive upper chars, "(OH)"\n        stack<int> stk; // record each used carry, "((H3)2)4", when reach H, stk = {4, 2}\n        for (int i = n - 1; i >= 0; --i) {\n            if (isdigit(formula[i])) {\n                flag = false;\n                int j = i;\n                while (i - 1 >= 0 && isdigit(formula[i - 1])) --i; // deal with case "Be32"\n                count = carry * stoi(formula.substr(i, j - i + 1));\n            } else if (formula[i] == \')\') {\n                if (i + 1 < n && isdigit(formula[i + 1])) {\n                    int k = i + 1;\n                    while (k + 1 < n && isdigit(formula[k + 1])) ++k; // deal with case "(Be)32"\n                    stk.push(stoi(formula.substr(i + 1, k - i)));\n                    carry *= stoi(formula.substr(i + 1, k - i));\n                } else stk.push(1);\n            } else if (formula[i] == \'(\') {\n                carry /= stk.top();\n                stk.pop();\n            } else if (isupper(formula[i])) {\n                if (flag) count = carry;\n                cur = formula[i];\n                int t = i;\n                while (t + 1 < n && islower(formula[t + 1])) {\n                    cur += formula[t + 1];\n                    ++t;\n                }\n                mp[cur] += count;\n                flag = true;\n            }\n        }\n        for (auto &m : mp) res += m.first + (m.second == 1 ? "" : to_string(m.second));\n        return res;\n    }\n};\n```
[]