C++ Easiest Solution with dry run | T: O(n) | S: O(n)
Intuition\nWhenenve you see brackets first data structure that should come in you mind is stack. So here We will use stack to solve this problem.\n\n# Approach\
# Intuition\nWhenenve you see brackets first data structure that should come in you mind is stack. So here We will use stack to solve this problem.\n\n# Approach\nTo keep the record of count in sorted way we will use map instead of unordered_map.\nHere we can read formula in two ways :\n1) from left to right\n2) from right to left \n\nAccording to me reading from right to left makes this problem easy.\nWe can multiply are top most number to what we will found next and hence work is done.\n\nTo explain concept i will directlydo dry run:\nLets say formula is K4(ON(SO3)2)2.This will cover all concepts\n```\ninitially: stack = ["1, ."]\nstart reading formula from back side.\nK4(ON(SO3)2)2\n            |\nso we will get 2 and next string after number is ).\n2*1=2 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "2, )"]\n\nK4(ON(SO3)2)2\n          |\nagain we get 2 and next string after number is ).\n2*2=4 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "2, )", "4, )"]\n\nK4(ON(SO3)2)2\n        |\nWe got 3 here and next string after number is O.\n4*3=12 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "2, )", "4, )","12, O"]\nnow our string which we have is "O" which is not \')\' and \'(\'. so we will pop this out and will update our map.\nmp[st.top().second]+=st.top().first;\nso our stack become: stack = ["1, .", "2, )", "4, )"]\nand O: 12\n\nK4(ON(SO3)2)2\n      |\nhere we din\'t get any number so our number is 1 and string is "S".\n1*4=4 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "2, )", "4, )","4, S"]\nnow our string which we have is "S" which is not \')\' and \'(\'. so we will pop this out and will update our map.\nmp[st.top().second]+=st.top().first;\nso our stack become: stack = ["1, .", "2, )", "4, )"]\nand O:12, S: 4\n\nK4(ON(SO3)2)2\n     |\nhere we din\'t get any number so our number is 1 and string is "(".\n1*4=4 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "2, )", "4, )","4, ("]\nbut the sting we found is \'(\' so we will pop two time to remove this open bracket and its correspondinf closing bracket.\n\nso our stack become: stack = ["1, .", "2, )"]\n\nK4(ON(SO3)2)2\n    |\nNow for N : so our stack become: stack = ["1, .", "2, )", "2, N"]\nwill pop it.\nstack = ["1, .", "2, )"]\nN:4 ,O:12, S: 4 \n\nK4(ON(SO3)2)2\n   |\nNow for O : so our stack become: stack = ["1, .", "2, )", "2, O"]\nwill pop it.\nstack = ["1, .", "2, )"]\nN:4 ,O:12+2=14, S: 4 \n\nK4(ON(SO3)2)2\n  |\nNow for ( : so our stack become: stack = ["1, .", "2, )", "2, ("]\nand it will pop 2 times stack become.\nstack = ["1, ."]\n\nK4(ON(SO3)2)2\n |\nWe got 4 here and next string after number is K.\n4*1=4 # we will check what is in stack and multiply the number with it\nso our stack becomes stack = ["1, .", "4, K"]\nnow our string which we have is "K" which is not \')\' and \'(\'. so we will pop this out and will update our map.\nmp[st.top().second]+=st.top().first;\nso our stack become: stack = ["1, ."]\nK:4, N:4, O: 14, S: 4 \n\nI guess you might have got he idea. If yes, don\'t forget to upvote.\n\n``` \n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string,int> mp;\n        stack<pair<int,string>> st;\n        string ans="";\n        st.push({1,"."});\n        for(int i=formula.size()-1;i>-1;i--){\n            int myint=0,k=1;\n            // getting number from back side\n            while(i>-1 && formula[i]<=\'9\' && \'0\'<=formula[i]){\n                myint=(formula[i]-\'0\')*k+myint;\n                k*=10;\n                i--;\n            }\n            // If there was no number let it be 1.\n            if(myint==0){\n                myint=1;\n            }\n            if(i>-1){\n                // Getting the element symbol having more than one character like Mg.\n                string myele="";\n                while(i>-1 && formula[i]>=97){\n                    myele=formula[i]+myele;\n                    i--;\n                }\n                myele=formula[i]+myele;\n                // pushing the element with count we got\n                st.push({st.top().first*myint,myele});\n\n                if(formula[i]!=\')\'){\n                    if(formula[i]!=\'(\'){\n                        // pop if its not parentheses and update map\n                        mp[st.top().second]+=st.top().first;\n                        st.pop();\n                    }\n                    else{\n                        // if we get \'(\' pop two time to remove this and its corresponding closing bracket\n                        st.pop();\n                        st.pop();\n                    }\n                }\n                else{\n                    // Don nothong if we get \')\' no need of else \n                    continue;\n                }\n            }\n        }\n        // form the output string for the output\n        for(auto i:mp){\n            if(i.second!=1)\n                ans+=i.first+to_string(i.second);\n            else\n                ans+=i.first;\n        }\n        return ans;\n\n    }\n};\n```
['String', 'Stack', 'Ordered Map', 'C++']