Efficient Parsing and Counting of Chemical Formulae Using Stacks.
Optimizations\nI really struggled through this problem and I honestly dont think my code is the most optimized code out there, Please suggest ways to optimize m
# Optimizations\nI really struggled through this problem and I honestly dont think my code is the most optimized code out there, Please suggest ways to optimize my solutions, Suggestions are always welcome.\n\n# Intuition\nThe problem is to count the number of each type of atom in a chemical formula and return the result in a canonical string format. The formula can contain parentheses, which denote groups of atoms that can appear multiple times. The solution involves parsing the formula, handling nested groups using stacks, and keeping track of atom counts.\n\n# Approach\n1) Tokenize the String: Traverse the input string and break it into tokens where each token is either an atom or a number. Handle multi-character atoms (e.g., Mg) and numbers that follow atoms.\n\n\n2) Track Frequencies: Use a stack to track the counts of atoms. When encountering an opening parenthesis (, push it to the stack. For a closing parenthesis ), multiply the counts of the elements inside the parentheses by the following number (if any).\n\n\n3) Build the Result: Once the parsing and counting are complete, aggregate the counts of each atom using a map. Convert the counts to the required format and return the final string.\n\n# Detailed Explanation of the Approach\n1) Initialization: Use a vector container to store tokens (atoms and numbers).Use elementswithfreq to store pairs of atoms and their frequencies.\n\n2) Tokenization: Traverse the string s, and split it into tokens of elements and numbers, storing them in container.\nRemove any parentheses tokens from container.\n\n3) Frequency Assignment:For each token, determine if it ends with a number (frequency). If not, assign a default frequency of 1.\n\n4) Stack Processing: Traverse the original string and use stacks to handle nested structures and multipliers for grouped elements.\nPush atoms with their frequencies onto the stack. For closing parentheses, calculate the new frequencies and re-push them onto the stack.\n\n5) Final Aggregation:Use a map to aggregate frequencies of the same atoms.\nConvert the map to a sorted vector and build the final result string.\n\n# Complexity\n- Time complexity:\nO(N log (N)) Collecting and Sorting\n\n- Space complexity:\nO(N) All linear Data Structures we have used here.\n\n# Code\n```\n#include <bits/stdc++.h>\nusing namespace std;\n#define nline \'\\n\'\n#define sp \' \'\n#define all(x) x.begin(), x.end()\n#define rall(x) x.rbegin(), x.rend()\nstatic int fastIO = []\n{\n    ios_base::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    return 0;\n}();\n\nclass Solution\n{\npublic:\n    string countOfAtoms(string s)\n    {\n        int n = s.length();\n        string temp = "";\n        temp += s[0];\n        vector<string> container;\n        for (int i = 1; i < n; i++)\n        {\n            if ((s[i] >= \'a\' && s[i] <= \'z\') || (s[i] >= \'0\' && s[i] <= \'9\'))\n            {\n                temp += s[i];\n            }\n            else\n            {\n                container.push_back(temp);\n                temp.clear();\n                temp += s[i];\n            }\n        }\n        container.push_back(temp);\n        for (int i = 0; i < container.size(); i++)\n        {\n            if (container[i][0] == \'(\' || container[i][0] == \')\')\n            {\n                container.erase(container.begin() + i);\n                i--;\n            }\n        }\n        vector<pair<string, int>> elementswithfreq;\n        for (string &cont : container)\n        {\n            string freq = "";\n            while (!cont.empty() && cont.back() >= \'0\' && cont.back() <= \'9\')\n            {\n                freq += cont.back();\n                cont.pop_back();\n            }\n            reverse(all(freq));\n            int f = freq.empty() ? 1 : stoi(freq);\n            elementswithfreq.push_back({cont, f});\n        }\n\n        stack<pair<string, int>> stk1;\n        stack<pair<string, int>> stk2;\n        int ind = 0;\n        for (int i = 0; i < n; i++)\n        {\n            if (s[i] >= \'A\' && s[i] <= \'Z\')\n            {\n                stk1.push({elementswithfreq[ind].first, elementswithfreq[ind].second});\n                ind++;\n            }\n            else if (s[i] == \'(\')\n            {\n                stk1.push({"(", -1});\n            }\n            else if (s[i] == \')\')\n            {\n                string number = "";\n                int x = i + 1;\n                while (x < n && s[x] >= \'0\' && s[x] <= \'9\')\n                {\n                    number += s[x];\n                    x++;\n                }\n                int multiply = number.empty() ? 1 : stoi(number);\n                while (stk1.top().first != "(")\n                {\n                    int newfreq = stk1.top().second * multiply;\n                    stk2.push({stk1.top().first, newfreq});\n                    stk1.pop();\n                }\n                if (stk1.top().first == "(")\n                {\n                    stk1.pop();\n                    while (!stk2.empty())\n                    {\n                        stk1.push(stk2.top());\n                        stk2.pop();\n                    }\n                }\n                i = x - 1;\n            }\n        }\n\n        vector<pair<string, int>> finalcontainer;\n        unordered_map<string, int> freqMap;\n        while (!stk1.empty())\n        {\n            freqMap[stk1.top().first] += stk1.top().second;\n            stk1.pop();\n        }\n        for (const auto &entry : freqMap)\n        {\n            finalcontainer.push_back(entry);\n        }\n        sort(all(finalcontainer));\n\n        string Res = "";\n        for (const auto &p : finalcontainer)\n        {\n            Res += p.first;\n            if (p.second != 1)\n            {\n                Res += to_string(p.second);\n            }\n        }\n        return Res;\n    }\n};\n\n```\n# Upvote?\n![upvote meme.jpg](https://assets.leetcode.com/users/images/3b7daaba-b4de-4d6d-8fd7-d467a481a955_1720946711.7374337.jpeg)\n
['C++']