[C++] Recursive Parser
\n/**\n * formula :\n *     unit[]\n * unit :\n *     atom (count)\n *     '(' formula ')' count\n * atom :\n *    upper (lower[])\n * count :\n *    digit[]\n 
```\n/**\n * formula :\n *     unit[]\n * unit :\n *     atom (count)\n *     '(' formula ')' count\n * atom :\n *    upper (lower[])\n * count :\n *    digit[]\n * -----------------------------\n * upper : '[A-Z]'\n * lower : '[a-z]'\n * digit : '[0-9]'\n */\n```\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        string output;\n        const int n = formula.size();\n        int i = 0;\n        map<string, int> counts = parseFormula(formula, i);\n        for (pair<string, int> p : counts) {\n            output += p.first;\n            if (p.second > 1) output += to_string(p.second);\n        }\n        return output;\n    }\n\nprivate:\n    map<string, int> parseFormula(string& s, int& i) {\n        map<string, int> counts;\n        const int n = s.size();\n        while (i < n && s[i] != ')') {\n            map<string, int> cnts = parseUnit(s, i);\n            merge(counts, cnts, 1);\n        }\n        return counts;\n    }\n\n    map<string, int> parseUnit(string& s, int& i) {\n        map<string, int> counts;\n        const int n = s.size();\n        if (s[i] == '(') {\n            map<string, int> cnts = parseFormula(s, ++i); // ++i for '('\n            int digits = parseDigits(s, ++i); // ++i for ')'\n            merge(counts, cnts, digits);\n        }\n        else {\n            int i0 = i++; // first letter\n            while (i < n && islower(s[i])) { i++; }\n            string atom = s.substr(i0, i - i0);\n            int digits = parseDigits(s, i);\n            counts[atom] += digits;\n        }\n        return counts;\n    }\n\n    int parseDigits(string& s, int& i) {\n        int i1 = i;\n        while (i < s.size() && isdigit(s[i])) { i++; }\n        int digits = i == i1 ? 1 : stoi(s.substr(i1, i - i1));\n        return digits;\n    }\n\n    void merge(map<string, int>& counts, map<string, int>& cnts, int times) {\n        for (pair<string, int> p : cnts) counts[p.first] += p.second * times;\n    }\n};\n```
[]