Python3. Parse the expression
Intuition\nProcess the expression. Use state machine for the parser, and stack to store the "(" and ")".\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space co
# Intuition\nProcess the expression. Use state machine for the parser, and stack to store the "(" and ")".\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n\nclass ParserStates:\n    AT_START = 0\n    IN_ELEMENT = 1\n    IN_NUMBER_AFTER_ELEMENT = 2\n    IN_NUMBER_AFTER_CLOSED_PARENTHESIS = 3\n    AFTER_OPEN_PARENTHESIS = 4\n    AFTER_CLOSE_PARENTHESIS = 5\n\ndef process_AT_START(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        atomCountStack.append(Counter())\n        state = ParserStates.AFTER_OPEN_PARENTHESIS\n    elif a.isupper():\n        elemChars.append(a)\n        state = ParserStates.IN_ELEMENT\n    else:\n        raise ValueError("Formula must begin with ( or Upper case")\n    return state, curNum\n\ndef push_element(atomCountStack, elemChars, count=1):\n    atomCountStack[-1]["".join(elemChars)] += count\n    elemChars.clear()\n\ndef process_IN_ELEMENT(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        if len(elemChars) > 0:\n            push_element(atomCountStack, elemChars)\n        else:\n            raise ValueError("Element cannot be empty IN_ELEMENT before (")\n        atomCountStack.append(Counter())\n        state = ParserStates.AFTER_OPEN_PARENTHESIS\n    elif a == \')\':\n        if len(elemChars) > 0:\n            push_element(atomCountStack, elemChars)\n        else:\n            raise ValueError("Element cannot be empty IN_ELEMENT before (")\n        state = ParserStates.AFTER_CLOSE_PARENTHESIS\n    elif a.islower():\n        if len(elemChars) < 2:\n            elemChars.append(a)\n        else:\n            raise ValueError("The element cannot contain more than 2 characters")\n    elif a.isupper():\n        if len(elemChars) > 0:\n            push_element(atomCountStack, elemChars)\n            elemChars.append(a)\n        else:\n            raise ValueError("The element cannot be empty")\n    elif a.isdigit():\n        curNum = ord(a) - 48\n        state = ParserStates.IN_NUMBER_AFTER_ELEMENT\n        if curNum == 0:\n            raise ValueError("Digital Index cannot start with 0")\n    else:\n        raise ValueError("Following characters of the element cannot be upper case")\n    return state, curNum\n\ndef process_IN_NUMBER_AFTER_ELEMENT(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        push_element(atomCountStack, elemChars, curNum)\n        atomCountStack.append(Counter())\n        state = ParserStates.AFTER_OPEN_PARENTHESIS\n    elif a == \')\':\n        push_element(atomCountStack, elemChars, curNum)\n        elemChars.clear()\n        state = ParserStates.AFTER_CLOSE_PARENTHESIS\n    elif a.isdigit():\n        curNum = ord(a) - 48 + 10 * curNum\n    elif a.isupper():\n        atomCountStack[-1]["".join(elemChars)] += curNum\n        elemChars.clear()\n        elemChars.append(a)\n        state = ParserStates.IN_ELEMENT\n    else:\n        raise ValueError("Element cannot start with lower case")\n    return state, curNum\n\ndef push_back_the_counter(atomCountStack, count=1):\n    lst = atomCountStack.pop()\n    prev = atomCountStack[-1]\n    for el, cnt in lst.items():\n        prev[el] += cnt * count\n\ndef process_IN_NUMBER_AFTER_CLOSED_PARENTHESIS(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        push_back_the_counter(atomCountStack, curNum)\n        atomCountStack.append(Counter())\n        state = ParserStates.AFTER_OPEN_PARENTHESIS\n    elif a == \')\':\n        push_back_the_counter(atomCountStack, curNum)\n        state = ParserStates.AFTER_CLOSE_PARENTHESIS\n    elif a.isdigit():\n        curNum = ord(a) - 48 + 10 * curNum\n    elif a.isupper():\n        push_back_the_counter(atomCountStack, curNum)\n        elemChars.append(a)\n        state = ParserStates.IN_ELEMENT\n    else:\n        raise ValueError("Element cannot start with lower case")\n    return state, curNum\n\ndef process_AFTER_OPEN_PARENTHESIS(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        atomCountStack.append(Counter())\n    elif a == \')\':\n        raise ValueError("Parentheses cannot be empty")\n    elif a.isdigit():\n        raise ValueError("Index cannot follow the open parenthesis")\n    elif a.isupper():\n        elemChars.append(a)\n        state = ParserStates.IN_ELEMENT\n    else:\n        raise ValueError("Element cannot start with lower case")\n    return state, curNum\n\n\ndef process_AFTER_CLOSE_PARENTHESIS(a, atomCountStack, state, elemChars, curNum):\n    if a == \'(\':\n        push_back_the_counter(atomCountStack)\n        atomCountStack.append(Counter())\n        state = ParserStates.AFTER_OPEN_PARENTHESIS\n    elif a == \')\':\n        push_back_the_counter(atomCountStack)\n        state = ParserStates.AFTER_CLOSE_PARENTHESIS\n    elif a.isdigit():\n        curNum = ord(a) - 48\n        state = ParserStates.IN_NUMBER_AFTER_CLOSED_PARENTHESIS\n    elif a.isupper():\n        push_back_the_counter(atomCountStack)\n        elemChars.append(a)\n        state = ParserStates.IN_ELEMENT\n    else:\n        raise ValueError("Element cannot start with lower case")\n    return state, curNum\n\n\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        atomCountStack = [Counter()]\n\n        elemChars = []\n        curNum = 0\n        state = ParserStates.AT_START\n\n        for a in formula:\n            match state:\n                case ParserStates.AT_START:\n                    state, curNum = process_AT_START(a, atomCountStack, state, elemChars, curNum)\n                case ParserStates.IN_ELEMENT:\n                    state, curNum = process_IN_ELEMENT(a, atomCountStack, state, elemChars, curNum)\n                case ParserStates.IN_NUMBER_AFTER_ELEMENT:\n                    state, curNum = process_IN_NUMBER_AFTER_ELEMENT(a, atomCountStack, state, elemChars, curNum)\n                case ParserStates.IN_NUMBER_AFTER_CLOSED_PARENTHESIS:\n                    state, curNum = process_IN_NUMBER_AFTER_CLOSED_PARENTHESIS(a, atomCountStack, state, elemChars, curNum)\n                case ParserStates.AFTER_OPEN_PARENTHESIS:\n                    state, curNum = process_AFTER_OPEN_PARENTHESIS(a, atomCountStack, state, elemChars, curNum)\n                case ParserStates.AFTER_CLOSE_PARENTHESIS:\n                    state, curNum = process_AFTER_CLOSE_PARENTHESIS(a, atomCountStack, state, elemChars, curNum)\n\n        match state:\n            case ParserStates.IN_ELEMENT:\n                state, curNum = process_IN_ELEMENT("A", atomCountStack, state, elemChars, curNum)\n            case ParserStates.IN_NUMBER_AFTER_ELEMENT:\n                state, curNum = process_IN_NUMBER_AFTER_ELEMENT("A", atomCountStack, state, elemChars, curNum)\n            case ParserStates.IN_NUMBER_AFTER_CLOSED_PARENTHESIS:\n                state, curNum = process_IN_NUMBER_AFTER_CLOSED_PARENTHESIS("A", atomCountStack, state, elemChars, curNum)\n            case ParserStates.AFTER_OPEN_PARENTHESIS:\n                raise ValueError("Invalid open parenthesis at the end")\n            case ParserStates.AFTER_CLOSE_PARENTHESIS:\n                state, curNum = process_AFTER_CLOSE_PARENTHESIS("A", atomCountStack, state, elemChars, curNum)\n\n        if len(atomCountStack) != 1:\n            raise ValueError("Only one counter should remain")\n\n        return "".join(el if cnt == 1 else el + str(cnt) for el, cnt in sorted(atomCountStack[-1].items()))\n```
['Python3']