Easy C++ Solution Using Stack with video explanation
Video Explanation\nhttps://youtu.be/17rme5dxX5o?si=PaNpUgilM6Cn6d1e\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requ
# Video Explanation\nhttps://youtu.be/17rme5dxX5o?si=PaNpUgilM6Cn6d1e\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires parsing a chemical formula string that contains element symbols and possibly nested parentheses. Each element symbol might be followed by an optional number indicating the number of atoms. Parentheses might enclose parts of the formula, potentially followed by a number that acts as a multiplier for the entire group.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Reverse Traversal: We\'ll traverse the formula string from right to left to easily handle multipliers and nested structures.\n2. Stack for Multipliers: A stack will help manage multipliers, especially when handling nested parentheses.\n3. Map for Atom Counts: We\'ll use a map to keep track of the counts of each atom.\n4. Handling Characters: We\'ll handle different character types:\n- Digits: Update the current count.\n- Letters: Build the atom name, update counts in the map.\n- Parentheses: Manage the multipliers using the stack.\n# Complexity\n- Time complexity:$$\uD835\uDC42(n+klogk)$$\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# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        map<string, int> aCount;\n        stack<int> mStack;\n        string result;\n        int count = 0, multiplier = 1;\n        \n        for (int i = size(formula) - 1; i >= 0; i--) \n        {\n            if (isalpha(formula[i]) && islower(formula[i])) \n            {\n                int len = 2;\n                i--;\n                \n                while (i >= 0 && islower(formula[i])) \n                {\n                    i--;\n                    len++;\n                }\n                \n                string atom = formula.substr(i, len);\n                aCount[atom] += max(count, 1) * multiplier;\n                count = 0;\n            } \n            else if (isalpha(formula[i]) && isupper(formula[i])) \n            {\n                string atom(1, formula[i]);\n                aCount[atom] += max(count, 1) * multiplier;\n                count = 0;\n            } \n            else if (isdigit(formula[i])) \n            {\n                count = formula[i] - \'0\';\n                int power = 10;\n                \n                while (i - 1 >= 0 && isdigit(formula[i - 1])) {\n                    count += power * (formula[--i] - \'0\');\n                    power *= 10;\n                }\n            } \n            else if (formula[i] == \')\') \n            {\n                mStack.push(multiplier);\n                multiplier *= max(count, 1);\n                count = 0;\n            } \n            else {\n                multiplier = mStack.top();\n                mStack.pop();\n            }\n        }\n        \n        for (auto [atom, cnt]: aCount) {\n            result += atom;\n            \n            if (cnt > 1) {\n                result += to_string(cnt);\n            }\n        }\n        \n        return result;\n    }\n};\n```
['C++']