[Heave Implementation + Stack Tutorial] Number of Atoms
Topic :  Simulation + Stack\n___\n\n## Solution\nBefore proceeding with any processing, it\'s important to note a few observations about the input:\n1. Each che
**Topic** :  Simulation + Stack\n___\n\n## Solution\nBefore proceeding with any processing, it\'s important to note a few observations about the input:\n1. Each chemical element must begin with an uppercase letter followed optionally by zero or one lowercase letter.\n2. Each chemical element or closing parenthesis `)` may be followed by a number. This number can consist of one or more digits.\n\nThe approach to solve the problem is straightforward: we utilize a stack where each element represents information about a chemical element and its count. As we iterate through the input string, we continuously add elements and their respective counts to this stack. \n\n1. It\'s true that **a chemical element always starts with an uppercase letter**. Therefore, when processing each character, we need to check whether the next character is lowercase or a digit.If the next character is a lowercase letter, the chemical element name is formed by concatenating s[i] and s[i + 1]. If the next character is a digit, we need to parse all consecutive digits starting from that position, which represent the count of that element.\n\n2. When **encountering a closing parenthesis** `)`, we multiply the count of each element currently in the stack by the number immediately following the parenthesis. We first parse all consecutive digits starting from the next position, which represent the multiplier. If there are no digits following it, the multiplier is assumed to be 1. After identifying the matching open parenthesis, we pop all elements from the stack before it, multiply their counts by the multiplier, and then insert them back into the stack with the updated counts.\n\nIt\'s important to note that at the final stage, we use a map because there may be multiple duplicate elements, and we need to aggregate their counts.\n\n**Unfortunately, the current implementation is too intensive, and there are no alternative programming languages available yet.**\n\n<br/><br/>\n\n```c++ []\nclass Solution {\npublic:\n    string countOfAtoms(string s) {\n        int n = s.size();\n        vector<pair<string, int>> stk;\n        for(int i = 0; i < s.size(); i++) {\n            if(s[i] == \'(\') {\n                stk.push_back({string(1, s[i]), 0});\n            } else if(s[i] == \')\') {\n                int mul = 0; //Find the multiplier\n                while(i + 1 < n && isDigit(s[i + 1])) {\n                    mul = mul * 10 + s[i + 1] - \'0\';\n                    i++;\n                }\n                if(mul == 0) mul = 1;\n                \n                vector<pair<string, int>> temp;\n                while(stk.size() > 0 && stk.back().first != "(") {\n                    pair<string, int>& p = stk.back(); stk.pop_back();\n                    p.second *= mul;\n                    temp.push_back(p);\n                }\n                stk.pop_back();\n                for(auto& p : temp) stk.push_back(p);\n            } else {\n                if(i + 1 < n) {\n                    string name(1, s[i]);\n                    int count = 0;\n                    if(isLower(s[i + 1])) {\n                        name += s[i + 1];\n                        i++;\n                    }\n                    //Find the count, similar as above for finding the mutiplier\n                    while(i + 1 < n && isDigit(s[i + 1])) {\n                        count = count * 10 + s[i + 1] - \'0\';\n                        i++;\n                    }\n                    if(count == 0) count = 1;\n                    stk.push_back({name, count});\n                } else { //A signel character represent an element\n                    stk.push_back({string(1, s[i]), 1});\n                }\n            }\n        }\n        \n        //re-construct the result\n        //We need to remove duplicate strings\n        map<string, int> mp;\n        for(auto& p : stk) mp[p.first] += p.second;\n        \n        string ans = "";\n        for(auto it = mp.begin(); it != mp.end(); it++) {\n            ans += it -> first;\n            if(it -> second > 1) ans += to_string(it -> second);\n        }\n        return ans;\n        \n    }\n    \n    bool isDigit(char c) {\n        return c - \'0\' >= 0 && c - \'0\' <= 9;\n    }\n    \n    bool isUpper(char c) {\n       return c - \'A\' >= 0 && c - \'A\' <= 25; \n    }\n    \n    bool isLower(char c) {\n       return c - \'a\' >= 0 && c - \'a\' <= 25; \n    }\n};\n```\n```Java []\nclass Solution {\n    public String countOfAtoms(String s) {\n        int n = s.length();\n        Stack<Pair<String, Integer>> stk = new Stack<>();\n        \n        for (int i = 0; i < n; i++) {\n            char ch = s.charAt(i);\n            if (ch == \'(\') {\n                stk.push(new Pair<>(String.valueOf(ch), 0));\n            } else if (ch == \')\') {\n                int mul = 0;\n                while (i + 1 < n && Character.isDigit(s.charAt(i + 1))) {\n                    mul = mul * 10 + (s.charAt(i + 1) - \'0\');\n                    i++;\n                }\n                if (mul == 0) mul = 1;\n                \n                Stack<Pair<String, Integer>> temp = new Stack<>();\n                while (!stk.isEmpty() && !stk.peek().getKey().equals("(")) {\n                    Pair<String, Integer> p = stk.pop();\n                    p = new Pair<>(p.getKey(), p.getValue() * mul);\n                    temp.push(p);\n                }\n                stk.pop();\n                while(temp.size() > 0) stk.push(temp.pop());\n            } else {\n                if (i + 1 < n) {\n                    String name = String.valueOf(ch);\n                    if(Character.isLowerCase(s.charAt(i + 1))) {\n                        name += s.charAt(i + 1);\n                        i++;\n                    }\n                    int count = 0;\n                    while(i + 1 < n && Character.isDigit(s.charAt(i + 1))) {\n                        count = count * 10 + (s.charAt(i + 1) - \'0\');\n                        i++;\n                    }\n                    if(count == 0) count = 1;\n                    stk.push(new Pair<>(name, count));\n                } else {\n                    stk.push(new Pair<>(String.valueOf(ch), 1));\n                }\n            }\n        }\n        \n        // Reconstruct the result\n        Map<String, Integer> mp = new TreeMap<>();\n        while (!stk.isEmpty()) {\n            Pair<String, Integer> p = stk.pop();\n            mp.put(p.getKey(), mp.getOrDefault(p.getKey(), 0) + p.getValue());\n        }\n        \n        StringBuilder sb = new StringBuilder();\n        for (Map.Entry<String, Integer> entry : mp.entrySet()) {\n            sb.append(entry.getKey());\n            if (entry.getValue() > 1) {\n                sb.append(entry.getValue());\n            }\n        }\n        \n        return sb.toString();\n    }\n}\n```\n```Python []\nclass Solution:\n    def countOfAtoms(self, s: str) -> str:\n        def is_digit(c):\n            return \'0\' <= c <= \'9\'\n        \n        def is_upper(c):\n            return \'A\' <= c <= \'Z\'\n        \n        def is_lower(c):\n            return \'a\' <= c <= \'z\'\n        \n        n = len(s)\n        stk = []\n        i = 0\n        \n        while i < n:\n            if s[i] == \'(\':\n                stk.append((s[i], 0))\n                i += 1\n            elif s[i] == \')\':\n                i += 1\n                mul = 0\n                while i < n and is_digit(s[i]):\n                    mul = mul * 10 + int(s[i])\n                    i += 1\n                if mul == 0:\n                    mul = 1\n                \n                temp = []\n                while stk and stk[-1][0] != \'(\':\n                    name, count = stk.pop()\n                    count *= mul\n                    temp.append((name, count))\n                stk.pop()  # Remove \'(\'\n                \n                for name, count in temp:\n                    stk.append((name, count))\n            else:\n                if i + 1 < n and is_lower(s[i + 1]):\n                    name = s[i] + s[i + 1]\n                    i += 2\n                else:\n                    name = s[i]\n                    i += 1\n                \n                count = 0\n                while i < n and is_digit(s[i]):\n                    count = count * 10 + int(s[i])\n                    i += 1\n                if count == 0:\n                    count = 1\n                \n                stk.append((name, count))\n        \n        # Reconstruct the result\n        mp = {}\n        for name, count in stk:\n            mp[name] = mp.get(name, 0) + count\n        \n        result = []\n        for name, count in sorted(mp.items()):\n            result.append(name)\n            if count > 1:\n                result.append(str(count))\n        \n        return \'\'.join(result)\n```\n\n\n**Complexity**:\n* Time Complexity : `O(n ^ 2)`\n* Space Complexity : `O(n)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['Python', 'Java']