Beats 100% users | Simple solution by using two stacks and map
Intuition\nThe objective is to parse a chemical formula string and count the number of each atom. The formula may include nested groups of atoms enclosed in par
# Intuition\nThe objective is to parse a chemical formula string and count the number of each atom. The formula may include nested groups of atoms enclosed in parentheses, with possible multipliers for these groups. Proper handling of nested structures and applying multipliers correctly is key to solving this problem.\n\n# Approach\n1. Stack Usage: We use two stacks:\nelementStack to keep track of atoms and their counts.\nmultiplierStack to keep track of multipliers when encountering nested groups indicated by parentheses.\n\n2. Parsing: We parse the string character by character:\nIf we encounter an atom, we parse its name and count, then push it onto the elementStack.\nIf we encounter \'(\', we push a special marker ("(", 0) onto the elementStack.\nIf we encounter \')\', we determine the corresponding multiplier and push (")", multiplier) onto the elementStack.\n\n3. Processing Stacks: After parsing, we process the elementStack:\nIf we encounter \')\', we update the currentMultiplier by multiplying the counts of elements within the corresponding parentheses by the multiplier and push the count onto the multiplierStack.\nIf we encounter \'(\', we divide the currentMultiplier by the top element of multiplierStack and pop the multiplierStack.\nOtherwise, we multiply the count of the element by currentMultiplier and add it to the elementCount map.\nWe pop the top element at each iteration.\n\n4. Constructing Result: Finally, we construct the result string by iterating through the elementCount map, sorting atoms lexicographically, and appending their counts if greater than 1.\n\n# Complexity\n- Time complexity:\nO(n), where n is the length of the string. Each character is processed once.\n\n- Space complexity:\nO(n), due to the use of stacks for storing elements and multipliers.\n\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        int n = formula.size();\n        string result = "";\n        map<string, int> elementCount;  // To store final counts of each element\n        stack<pair<string, int>> elementStack;  // To store elements and their counts\n        stack<int> multiplierStack;  // To store multipliers for nested structures\n        int currentMultiplier = 1;  // Current multiplier for nested elements\n        int i = 0;\n\n        // Parse the formula\n        while (i < n) {\n            string element = "", countStr = "";\n            int j = i;\n\n            // Parse element name and its count\n            if (formula[i] >= \'A\' && formula[i] <= \'Z\') {\n                element += formula[i];\n                j = i + 1;\n                while (j < n && formula[j] >= \'a\' && formula[j] <= \'z\') {\n                    element += formula[j];\n                    j++;\n                }\n                while (j < n && formula[j] >= \'0\' && formula[j] <= \'9\') {\n                    countStr += formula[j];\n                    j++;\n                }\n                if (countStr == "") {\n                    elementStack.push({element, 1});\n                } \n                else {\n                    elementStack.push({element, stoi(countStr)});\n                }\n                i = j;\n            } \n            else if (formula[i] == \'(\') {\n                elementStack.push({"(", 0});\n                i++;\n            } \n            else if (formula[i] == \')\') {\n                j = i + 1;\n                while (j < n && formula[j] >= \'0\' && formula[j] <= \'9\') {\n                    countStr += formula[j];\n                    j++;\n                }\n                int multiplier = (countStr == "") ? 1 : stoi(countStr);\n                elementStack.push({")", multiplier});\n                i = j;\n            }\n        }\n\n        // Process the elements in the stack and apply multipliers\n        while (!elementStack.empty()) {\n            string element = elementStack.top().first;\n            int count = elementStack.top().second;\n            if (element == ")") {\n                currentMultiplier *= count;\n                multiplierStack.push(count);\n            } \n            else if (element == "(") {\n                currentMultiplier /= multiplierStack.top();\n                multiplierStack.pop();\n            } \n            else {\n                int adjustedCount = currentMultiplier * elementStack.top().second;\n                elementCount[element] += adjustedCount;\n                \n            }\n            elementStack.pop();\n        }\n\n        // Build the result string\n        for (auto& elem : elementCount) {\n            result += elem.first;\n            if (elem.second != 1) {\n                result += to_string(elem.second);\n            }\n        }\n\n        return result;\n    }\n};\n```
['Stack', 'Ordered Map', 'C++']