726. 原子的数量

给定一个化学式formula（作为字符串），返回每种原子的数量。

原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。

两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。

一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

示例 1:

输入: 
formula = "H2O"
输出: "H2O"
解释: 
原子的数量是 {'H': 2, 'O': 1}。

示例 2:

输入: 
formula = "Mg(OH)2"
输出: "H2MgO2"
解释: 
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。

示例 3:

输入: 
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释: 
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

注意:

• 所有原子的第一个字母为大写，剩余字母都是小写。
• formula的长度在[1, 1000]之间。
• formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。

栈 困难

用栈处理括号，再统计输出即可

代码

因为样例长度不超过1000，所以两种代码差别不会很大。

1. 我的代码

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        n = len(formula)
        stack = []
        i = 0
        while i < n:
            c = formula[i]
            stack.append(c)
            if c.isalpha():
                if (i < n-1 and not formula[i+1].isdigit() and not formula[i+1].islower()) or i == n-1:
                    stack.append('1')
            if c == ')':
                stack.pop()
                # m = int(formula[i+1])
                m = ''
                while i < n-1  and formula[i+1].isdigit():
                    m += formula[i+1]
                    i += 1
                temp = ''
                while stack[-1] != '(':
                    t = stack.pop()
                    if t.isdigit():
                        while stack[-1].isdigit():
                            t = stack.pop() + t
                        if m:
                            t = str(int(t)*int(m)) 
                    temp = t + temp
                stack.pop()
                stack.extend(temp)    
            i += 1
        counter = Counter()
        element = ''
        i = 0
        n = len(stack)
        while i < n:
            c = stack[i]
            if c.isalpha():
                element += c
            else: 
                while i+1<n and stack[i+1].isdigit():
                    c += stack[i+1]
                    i += 1
                counter[element] += int(c)
                element = ''
                # i += 1 
            i += 1  
        counter = list(counter.items())
        counter.sort(key=lambda x:x[0])
        ans = ''
        for key,value in counter:
            if value == 1:
                ans += key
            else:
                ans += '%s%d'%(key,value)
        return ans

2. 倒着遍历

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        # 倒着的时候， 记录map，乘的基数，迭代中的乘数，个数，个数的10进制位数，元素
        cnts, multiply, muls, num, num_count, atom = defaultdict(int), 1, [], 0, 0, ""
        for c in formula[::-1]:
            if c == ')':
                # 如果当前有统计的数字，乘的基数要叠加
                if num:
                    multiply *= num
                    muls.append(num)
                    num = num_count = 0
                else:
                    muls.append(multiply)
            elif c == '(':
                # 去除掉上一个乘数
                multiply //= muls.pop()
            elif str.isdigit(c):
                num += int(c) * (10 ** num_count)
                num_count += 1
            elif str.islower(c):
                atom += c
            else:
                atom += c
                # 注意我们在更新元素个数时，始终要考虑乘的基数
                if num:
                    cnts[atom[::-1]] += num * multiply
                else:
                    cnts[atom[::-1]] += multiply
                atom = ""
                num = num_count = 0
        return "".join(key if cnts[key] == 1 else key + str(cnts[key]) for key in sorted(cnts.keys()))