[C++] Linear Scan with Stack.  Runtime: 0ms
This solution is based on how humans would parse and count these formulae, but in a sequential fashion.\n\nRuntime should be linear in the length of the string 
This solution is based on how humans would parse and count these formulae, but in a sequential fashion.\n\nRuntime should be linear in the length of the string plus a factor k ln(k) for k unique symbols in the string for inserting, modifying and deleting on a BST (a std::map). \n\nBasic idea is we maintain a stack of pairs<string, int> representing the current symbol plus its count.  When we find an open paren, we push it directly on the stack with a dummy count.  When we find a close paren, we create a temp stack, pop everything off the working stack until we reach "(" while multiplying its count value by whatever comes after the ")".  We then push this all back onto our working stack.\n\nAt the end, we tally everything in a map using a pair<string,int> as a key, plus-value pair until our working stack is empty.  Then we just walk the map adding everything into a string and ret the string.\n\nThis can probably be made theoretically faster by not using a dynamic sorting DS like a BST, but I was too lazy to come up with something more cache friendly\n\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string, int> m;\n        stack<pair<string,int>> st;\n        \n        string curr=""; //Building symbols\n        int num=0; //Counting\n        int i=0;//Index\n        \n        while (i<formula.size()){\n            char c=formula[i];\n            if (c==\'(\'){\n                //Open Bracket\n                curr="";\n                num=0;\n                st.emplace("(",0);\n                ++i;\n            }\n            \n            else if (c==\')\'){\n                stack<pair<string,int>> temp;\n                ++i;\n                \n                //Scan past the last paren to see if we have any numbers\n                while (i<formula.size() && isdigit(formula[i])){\n                    num=num*10+(formula[i]-\'0\');\n                    ++i;\n                }\n                //Multiply everything in between\n                while (st.top().first != "("){\n                    \n                    //num is 0 to make parsing work, but no num after symbols means 1\n\t\t\t\t\t\n                    temp.emplace(st.top().first, st.top().second*max(1,num)); \n                    st.pop();\n                }\n                \n                //reset\n                num=0;\n                \n                //Get rid of open Paren\n                st.pop();\n                \n                //Put stuff back\n                while (!temp.empty()){\n                    st.emplace(temp.top()); temp.pop();\n                }\n            }\n            \n            else if (isupper(c)){\n                //Parse Symbol plus immediate numbers\n                \n                curr+=c;\n                ++i;\n                while (i<formula.size() && islower(formula[i])){\n                    curr+=formula[i];\n                    ++i;\n                }\n                while (i<formula.size() && isdigit(formula[i])){\n                    num=num*10+formula[i]-\'0\';\n                    ++i;\n                }\n                st.emplace(curr, max(1,num));\n                curr="", num=0;\n            }\n        }\n        \n        //Add everything\n        while (!st.empty()){\n            m[st.top().first]+=st.top().second;\n            st.pop();\n        }\n        \n        //Already have a string around\n        curr="";\n        \n        for (auto& p : m){\n            curr+=p.first;\n            if (p.second>1) curr+=to_string(p.second);\n        }\n        return curr;\n    }\n};\n```
[]