Beats 100% || Easy C++ Solution
\n\n\n# Approach\nTo solve the problem of counting atoms in a chemical formula with nested parentheses, you can use a stack to keep track of the counts. Here\'s
![image.png](https://assets.leetcode.com/users/images/c8c34f5b-4265-4d3f-8966-f622676d586d_1720953649.6267164.png)\n\n\n# Approach\nTo solve the problem of counting atoms in a chemical formula with nested parentheses, you can use a stack to keep track of the counts. Here\'s a detailed approach:\n\n **Traverse the String from End to Start:**\n- If digit, read the full number (in case of multi-digit numbers).\n- If capital letter, read the full atom name (including possible lowercase letters).\n- If closing parenthesis \')\', push (**current count * top value of stack**) to the stack.\n- If opening parenthesis \'(\', pop the top value from the stack.\n\n**Example:** (K4(H2O)2)3\n***Traverse from End:***\n- \'3\': Read 3 onto the stack.\n- \')\': Push the current count onto the stack.\n- \'2\': Read 2 onto the stack.\n- \')\': Calculate the value. 2*(top value of the Stack) => 6 & Push the value onto the stack.\n- \'O\': \'O\' with count 1, increase the total with multipling by top value of the Stack.\n```\nif(!mul.empty()){\n    m[ch] += mul.top()*num2;\n}else{\n    m[ch] += num2;\n}\n```\n\n- \'H\': Same as \'O\'.\n- \'(\': Pop the top value from the stack.\n- Go on.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string,int> m;\n        stack<int> mul;\n        string num = "",ch = "";\n        for(int i = formula.size()-1;i>=0; i--){\n            char x = formula[i];\n            if(x >= \'A\' && x<= \'Z\'){\n                ch = x+ch;\n                if(ch != ""){\n                    int num2 = 1;\n                    if(num != "") num2 = stoi(num);\n                    if(!mul.empty()){\n                        m[ch] += mul.top()*num2;\n                    }else{\n                        m[ch] += num2;\n                    }\n                }\n                ch = "";\n                num = "";\n            }\n            else if(x >= \'a\' && x<= \'z\'){\n                ch = x+ch;\n            }\n            else if(x >= \'0\' && x<= \'9\'){\n                num = x+num;\n            }\n            else if(x == \'(\'){\n                if(!mul.empty()){\n                    mul.pop();\n                }\n                ch = "";\n                num = "";\n            }\n            else if(x == \')\'){\n                if(num != ""){\n                    int num1 = stoi(num);\n                    if(!mul.empty()){\n                        num1*=mul.top();\n                    }\n                    mul.push(num1);\n                }\n                num = "";\n                ch ="";\n            }\n        }\n        formula = "";\n        for(auto it = m.begin(); it != m.end(); it++){\n            formula+=it->first;\n            if(it->second >1) formula+=to_string(it->second);\n        }\n        return formula;\n    }\n};\n```
['C++']