Elegant & Clean C++  Iterative Solution Using stack ( via Reverse the Formula)
Aha, I think this is by far the cleanest solution.  The idea is very simple, reverse the formula and iteratively process the formula with the help of a stack re
Aha, I think this is by far the cleanest solution.  The idea is very simple, reverse the formula and iteratively process the formula with the help of a stack recording the multiplication factor of the current element.\n\nThe code is quite self-explanatory. Hope it helps!\n\n**Updated:**\n\nSpecial thanks to @xmeng525 to make it more clear.\n\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        std::map<string, int> stats;\n        std::reverse(formula.begin(), formula.end());\n        compute(formula, stats);\n        string result;\n        \n        for (auto& kv : stats) {\n            result += kv.first;\n            if (kv.second > 1) {\n                result += std::to_string(kv.second);\n            }\n        }\n        return result;\n    }\n    \nprivate: // K4(ON(SO3)2)2\n    void compute(string& formula, std::map<string, int>& stats) {\n        int n = formula.size();\n        \n        std::stack<int> stk; // factor\n        stk.push(1);\n        \n        string elem; // chemical element, e.g., C, N, O, Na, Mg, Al, etc.\n        int factor = 1; // number of this element, default to 1 if not otherwise specified\n        \n        for (int i = 0; i < n; ++i) {\n            auto& c = formula[i];\n            if (isdigit(c)) { // E.g., original 312 was reverse to 213.\n                int val = 0, expo = 1;\n                do {\n                    val += (c - '0') * expo;\n                    ++i; expo *= 10;\n                } while (isdigit(c = formula[i]));\n                factor = val; // explicit number of this element\n                \n                i -= 1;\n            } else if (c == ')') { \n                stk.push(factor * stk.top());\n                factor = 1; //            Al(OH)3\n            } else if (c >= 'A' && c <= 'Z') {\n                elem += c;\n                std::reverse(elem.begin(), elem.end());\n                stats[elem] += factor * stk.top();\n                factor = 1;\n                elem.clear();\n            } else if (c >= 'a' && c <= 'z') {\n                elem += c;\n            } else { // (c == '(') {  \n                stk.pop();  // Ca(OH)2\n                // elem.clear();\n            } \n        }   \n    }\n};\n```
[]