Given a string formula representing a chemical formula, return the count of each atom.

The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow.


	For example, "H2O" and "H2O2" are possible, but "H1O2" is impossible.


Two formulas are concatenated together to produce another formula.


	For example, "H2O2He3Mg4" is also a formula.


A formula placed in parentheses, and a count (optionally added) is also a formula.


	For example, "(H2O2)" and "(H2O2)3" are formulas.


Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

The test cases are generated so that all the values in the output fit in a 32-bit integer.

&nbsp;
Example 1:

Input: formula = "H2O"
Output: "H2O"
Explanation: The count of elements are {'H': 2, 'O': 1}.


Example 2:

Input: formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.


Example 3:

Input: formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation: The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.


&nbsp;
Constraints:


	1 &lt;= formula.length &lt;= 1000
	formula consists of English letters, digits, '(', and ')'.
	formula is always valid.


from collections import Counter, deque

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        """
        parser:
            formula: elem {count} formula
            elem: term | ( formula )
            term: [A-Z](a-z)+
            count: [0-9]+
        """
        
        
        def parse_formula(dq, allCount=Counter()):
            lhs = parse_elem(dq)
            count = 1
            while dq and dq[0].isdigit():
                count = parse_count(dq)
            for k in lhs.keys():
                allCount[k] += lhs[k] * count

            if dq and dq[0] not in ')':
                return parse_formula(dq, allCount)
            else:
                return allCount

        def parse_elem(dq):
            if dq and dq[0] == '(':
                dq.popleft()
                res = parse_formula(dq, Counter())
                dq.popleft()
                return res
            else:
                elem = ''
                if dq and dq[0].isupper():
                    elem += dq.popleft()
                    while dq and dq[0].islower():
                        elem += dq.popleft()
                return {elem: 1}

        def parse_count(dq):
            c = 0
            while dq and dq[0].isdigit():
                c = c * 10 + int(dq.popleft())
            return c

        formula = deque(formula)
        count_result = parse_formula(formula)
        result = ''
        for k in sorted(count_result.keys()):
            v = count_result[k]
            if v == 1:
                result += k
            else:
                result += f"{k}{count_result[k]}"
        return result
class Solution {
    public String countOfAtoms(String formula) {
        Deque<Integer> multiplier = new ArrayDeque<>();
        Map<String, Integer> map = new HashMap<>();
        int lastValue = 1;
        
        multiplier.push(1);
        
		// Iterate from right to left
        for (int i = formula.length() - 1; i >= 0; i--) {
            if (Character.isDigit(formula.charAt(i))) { // Case of a digit - Get full number and save
                StringBuilder sb = new StringBuilder();
				
                while (Character.isDigit(formula.charAt(i-1))) {
                    sb.append(formula.charAt(i));
                    i--;
                }
                sb.append(formula.charAt(i));
                lastValue = Integer.parseInt(sb.reverse().toString());
            } else if (formula.charAt(i) == ')') { // Start parenthesis - push next multiplier to stack
                multiplier.push(lastValue * multiplier.peek());
                lastValue = 1;
            } else if (formula.charAt(i) == '(') { // End parenthesis - pop last multiplier
                multiplier.pop();
            } else { // Case of an element name - construct name, update count based on multiplier
                StringBuilder sb = new StringBuilder();
                
                while (Character.isLowerCase(formula.charAt(i))) {
                    sb.append(formula.charAt(i));
                    i--;
                }
                sb.append(formula.charAt(i));
                
                String element = sb.reverse().toString();
                map.put(element, map.getOrDefault(element, 0) + lastValue * multiplier.peek());
                lastValue = 1;
            }
        }
        
		// Sort map keys
        List<String> elements = new ArrayList<>(map.keySet());
        StringBuilder sb = new StringBuilder();
        Collections.sort(elements);
        
		// Construct output
        for (String element : elements) {
            sb.append(element);
            if (map.get(element) > 1) {
                sb.append(map.get(element));       
            }
        }
        return sb.toString();
    }
}
class Solution {
public:
    // helper functions
    bool isUpper(char ch) {
        return ch >= 65 && ch <= 90;
    }

    bool isLower(char ch) {
        return ch >= 97 && ch <= 122;
    }

    bool isLetter(char ch) {
        return isUpper(ch) || isLower(ch);
    }

    bool isNumber(char ch) {
        return ch >= 48 && ch <= 57;
    }

    void addKey(map<string, long int>& count, string key, long int value) {
        if(count.find(key) != count.end()) {
            count[key] = count[key] + value;
        }
        else {
            count[key] = value;
        }
    }

    // very specific utility function
    string buildName(string formula, int& i) {
        string name = "";
        name.push_back(formula[i]);
        if(isUpper(formula[i])) {
            return name;
        }
        if(i == formula.length()-1) {
            return name;
        }
        while(isLower(formula[i-1])) {
            name.push_back(formula[i-1]);
            i--;
        }
        name.push_back(formula[i-1]);
        i--;
        reverse(name.begin(), name.end());
        return name;
     }

    // very specific utility function
    long int buildCount(string formula, int& i, vector<long int>& stack) {
        long int num = formula[i] - '0';
        long int place = 1;
        if(i == 0) {
            return num;
        }
        while(isNumber(formula[i-1])) {
            place = place * 10;
            num = (formula[i-1]-'0') * place + num;
            i--;
        }
        return num;
    }

    string countOfAtoms(string formula) {
        string ans;
        map<string, long int> count;
        vector<long int> stack;
        long int factor = 1;
        string name = "";
        long int num = -1; // -1 indicates a number reset, ie, count = 1

        // iterator i is passed by reference to keep track of
        // the substrings that are builded, ie, atom
        // names or numbers
        int i = formula.length()-1;
        while (i >= 0) {
            // here we need the number after the bracket close. This is
            // either 1 or num depending on whether we built a number before
            if(formula[i] == ')') {
                if(i+1 <= formula.length()-1 && isNumber(formula[i+1])) {
                    stack.push_back(num);
                    factor = factor * num;
                    num = -1;
                }
                else {
                    stack.push_back(1);
                }
            }
            // here is why we need a stack. Remove latest factor that was added.
            else if(formula[i] == '(') {
                factor = factor / stack.back();
                stack.pop_back();
            }
            // once we detect a letter, we know it can only be a word. num gives us the atom subscript
            // and factor gives us the molecular count.
            else if(isLetter(formula[i])) {
                name = buildName(formula, i);
                if(num == -1) {
                    addKey(count, name, 1 * factor);
                }
                else {
                    addKey(count, name, num * factor);
                }
                num = -1; // reset number
            }
            else if(isNumber(formula[i])) {
                num = buildCount(formula, i, stack);
            }
            i--;
        }

        // arrange name and count in a string
        map<string, long int>::iterator it;
        for (it = count.begin(); it != count.end(); it++)
        {
            ans = ans + it->first;
            if(it->second != 1) {
                ans = ans + to_string(it->second);
            }
        }
        return ans;
    }
};
var countOfAtoms = function(formula) {
    function getElementCount(flatFormula) {
        const reElementCount = /([A-Z][a-z]*)(\d*)/g;
        let matches = flatFormula.matchAll(reElementCount);
        
        let output = new Map();
        
        for (let [match, element, count] of matches) {
            count = count === '' ? 1 : +count;
            
            if (output.has(element)) {
                output.set(element, output.get(element) + count);
            } else {
                output.set(element, count);
            }
        }
        
        return output;
    }
    
    function flattenElementCount(elCountMap) {
        let arr = [...elCountMap.entries()].sort();
        
        return arr.reduce( (str, item) => {
            let num = item[1] === 1 ? '' : item[1];
            return str + item[0] + num;
        }, '' );
    }
    
    function unnest(fullMatch, innerFormula, multiplier) {
        let elementCount = getElementCount(innerFormula);
        multiplier = multiplier === '' ? 1 : +multiplier;
        
        for (let [element, count] of elementCount) {
            elementCount.set(element, elementCount.get(element) * multiplier);
        }
        
        return flattenElementCount(elementCount);
    }
    
    function flattenFormula(formula) {
        const reNested = /\((\w+)\)(\d*)/g;
        
        while (reNested.test(formula)) {
            formula = formula.replaceAll(reNested, unnest);
        }
        
        return formula;
    }
    
    let flatFormula = flattenFormula(formula);    
    
    return flattenElementCount(getElementCount(flatFormula));
};
Number of Atoms