efficient O(N) python3 solution, using stack of stacks with explanation of code and approach
Performance - https://leetcode.com/submissions/detail/522105544/\n\nEssentially the main idea is to create a new \'processing stack\' everytime we encounter a b
Performance - https://leetcode.com/submissions/detail/522105544/\n\nEssentially the main idea is to create a new \'processing stack\' everytime we encounter a bracket opening and process that stack when we see a closing bracket. After processing the stack we collapse the result into the parent stack from which the new processing stack was created. \n\nDoing the above steps would flatten the formula which will make the final counting a lot simpler.\n\nFor example - if we were given the formula `K4(ON(SO3)2)2`, here\'s how the algorithm would handle it.\n\nwe start with a top-level \'processing stack\' this stack is within a \'stack-of-stacks\'. This stack-of-stacks starts with one-processing stack in it. The atoms and their counts go into this top-level-processing-stack... until ... we see a bracket.\n\nso, initially\n`s=[[]]`\n\nwhen we parse out `K4` and are at the first `(`, our stack-of-stack will look like.\n`s=[[(\'K\',4)]]`\n\nwhen we see the `(` we create a new processing stack.\n`s=[[(\'K\',4)],[]]`\n\nthen we parse as usual so we wil have processed O,N when we encounter the second `(`. This wil cause the stack to look like this ...\n`s=[   [(\'K\',4)]   ,   [(O,1),(N,1)]   , [] ]`\n\nthen we process the `SO3` as usual and then encounter `)` at which point `s` looks like\n`s=[ [(K,4)] , [(O,1),(N,1)],  [(S,1), (O,3)] ]`\n\nseeing the `)` will indicate that we can collapse `[(S,1),(0,3)]` processing stack into it\'s parent `[(O,1),(N,1)]`\n\nbut before we do we need to see if that sub-formula has a multiplier or not, if it does, we will need to multiply each atom in that stack with the multiplier. So, we look ahead first by 1 character to determine if there is a number or not. In this case there is. So we update the `[(S,1),(O,3)]` by the multiplier `2`. Which will make it look like `[(S,2),(O,6)]`. At this point we can merge this stack with it\'s parent. So, s becomes.\n\n`s=[ [(K,4), [(O,1),(N,1), (S,2), (O,6)] ]` \n\nNext character is another `)`. So we look ahead by 1, parse out what it is, if it\'s a number, then we have a multiplier for our processing-stack. In this case we parse out `2`. So, we multiply every atom-count by `2` in `\n [(O,1),(N,1), (S,2), (O,6)]`, which will give us ` [(O,2),(N,2), (S,4), (O,12)]`. At this point we can collapse/merge this processing stack with it\'s parent, making `s` look like.\n \n`s=[ [(K,4),(O,2),(N,2), (S,4), (O,12)] ]`\n\nAt this point we are back to our top-level processing stack and have parsed and processed the entire formula. Now we just need to aggregate what we have in `s` and format it as per the question, which is relatively a lot more straight forward...\n\n```\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        # constant declarations\n        upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ"\n        lower=upper.lower()\n        digits = "0123456789"\n        \n        # variables\n        count=defaultdict(int)\n        element_name = None\n        element_name_parse_start=False\n        element_count =""\n        bracket_stacks = [[]]\n        buffer = []\n        \n        # function to parse out the complete number if a digit is seen, \n        # the function takes the character, that was seen as a digit and \n        # the generator object to get the remaining (yet to be read) part of formula\n        def parseout_number(ch,gen):\n            nonlocal buffer\n            num=""\n            try:\n                while ch in digits:\n                    num += ch\n                    ch = next(gen)\n                # after number is parsed out and a non-number character is seen, \n                # add that non-number character to the buffer to be read next, dont miss parsing it\n                buffer.append(ch)\n            except StopIteration:\n                # while iterating to find the end digit of the number, we have reached the end of the formula, \n                # meaning the digit ch and subsequent characters were numbers and were the last thing in the formula\n\t\t\t\t# the code, outside of try-catch handles all the possible scenerios of parsing the number out, \n\t\t\t\t# so do nothing here. move along\n                pass\n            # if we saw a number, return it as integer, else return empty string\n            if num != "":\n                return int(num)\n            else:\n                return ""\n        \n        #generator expression\n        formula_chars = (ch for ch in formula)\n        \n        # iterate over all characters\n        for char in formula_chars:\n            \n            # add the character emitted by generator into buffer for processing\n            buffer.append(char)\n            \n            # process what ever is in the buffer queue\n            while buffer:\n                ch = buffer.pop(0)\n                \n                # if the character is an upper case character\n                # set the a flag to indicate start of a new element name\n                # check if the previous elementname was added to the processing_stack (bracket_stacks)\n                # if not then add it, noting one atom for that element\n                # set the character to element_name variable\n                if ch in upper:\n                    element_name_parse_start=True\n                    if element_name is not None and element_count == "":\n                        bracket_stacks[-1].append([element_name,1])\n                    element_name = ch\n                # if character is lowercase, just concat it to the element_name\n                elif ch in lower:\n                    element_name += ch\n                # if character is a numerical digit, then parse that number out completely as integer\n                # set the flag to indicate the reading the element name is done\n                # store the element name and it\'s corresponding count into the processing_stack\n                # reset the variables element_name and element_count, ready for next element\n                elif ch in digits:\n                    element_name_parse_start=False\n                    element_count = parseout_number(ch,formula_chars)\n                    bracket_stacks[-1].append([element_name,element_count])\n                    element_count = ""\n                    element_name = None\n                # if open bracket is seen, check if reading the element_name flag is still True\n                # if it is then that element has one atom only\n                # add it to the processing stack\n                # set the flag to indicate that reading the \'element_name\' is done and \n                # add another processing stack top the top of the \'bracket_stacks\'\n                # this new processing stack will have the atom details within the bracket\n                # finally, reset all other variables to ensure \n\t\t\t\t# clean slate for the new child \'processing-stack\' before exiting the code-block\n                elif ch == "(":\n                    if element_name_parse_start:\n                        bracket_stacks[-1].append([element_name,1])\n                    element_name_parse_start=False\n                    element_count = ""\n                    bracket_stacks.append([]) # new processing stack\n                    element_name = None\n                \n                # if a bracket is closed\n                # make sure we account for one atom of element, if a number was not seen before closing the bracket\n                # set the flag to indicate we are done reading element_name\n                # check what is the next character after the bracket close char. \n\t\t\t\t# if it\'s a digit, then parse that number out \n                # that number is the multiplier for the current processing stack\n                # which means we will need to multiply every atom/element count by the multiplier\n                # at this point the current processing stack \n\t\t\t\t# which was created as part of opening the bracket is processed\n                # so, merge what we found into the parent processing stack by \n                # extending the parent processing stack with the results of the child stack\n                elif ch == ")":\n                    if element_name_parse_start:\n                        bracket_stacks[-1].append([element_name,1])\n                    element_name = None\n                    element_name_parse_start=False\n                    braket_multiplier = ""\n                    try:\n                        next_ch= next(formula_chars)\n                        braket_multiplier = parseout_number(next_ch,formula_chars)\n                    except StopIteration:\n                        pass\n                    \n                    if braket_multiplier == "":\n                        braket_multiplier = 1\n\t\t\t\t\t# pop the child processing - stack to be processed\n                    process_this = bracket_stacks.pop()\n                    \n\t\t\t\t\t#processing\n                    for idx,_ in enumerate(process_this):\n                        process_this[idx][1] = process_this[idx][1]*braket_multiplier\n\t\t\t\t\t\n\t\t\t\t\t#merging processed child stack with the parent stack\n                    bracket_stacks[-1].extend(process_this)\n        \n        # if the new element name seen flag is set then process that \n        # atom by adding it\'s element-name and atom count to the current processing stack\n        if element_name_parse_start:\n            if element_name is not None:\n                if element_count != "":\n                    bracket_stacks[-1].append([element_name,int(element_count)])\n                else:\n                    bracket_stacks[-1].append([element_name,1])\n        \n        # pop the top-level processing-stack, this should contain a \'flattened\' version of the atoms and their counts\n        # note that the counts of elements are not aggregated yet, \n        # eg:If Oxygen was seen within a bracket and also seen outside that bracket, \n        # then we\'ll have two entries for Oxygen. We\'ll aggregate them next...\n        count_pairs = bracket_stacks.pop()\n        \n        # aggregate all the \'flattened\' data in \'count_pairs\' variable, using a dictionary\n        for element_name,element_count in count_pairs:\n            count[element_name]+= element_count\n        \n        # preparing the output string...\n        # create a list meant to hold the \'words\' of the output string, based on the description\n        output=[]\n        \n        # fetch the keylist\n        elements_list = list(count.keys())\n        \n        #sort it\n        elements_list.sort()\n        \n        # for each element in the sorted keylist, if the element has more \n        # than 1 atom, append the atom and it\'s count\n        # if element has only 1 atom only append the atom name, \n        # but don\'t append the atom\'s count (which is 1)\n        for element in elements_list:\n            if count[element] > 1:\n                output.append(element)\n                output.append(str(count[element]))\n            else:\n                output.append(element)\n        \n        # output will now have an list of words representation of what we need. turn the list into a string and return it\n        return "".join(output)\n```
['Stack', 'Python', 'Python3']