1.题目基本信息

1.1.题目描述

给你一个字符串化学式 formula ，返回 每种原子的数量 。

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

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。

• 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。

两个化学式连在一起可以构成新的化学式。

• 例如 "H2O2He3Mg4" 也是化学式。

由括号括起的化学式并佐以数字（可选择性添加）也是化学式。

• 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。

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

1.2.题目地址

https://leetcode.cn/problems/number-of-atoms/description/

2.解题方法

2.1.解题思路

栈+哈希表

2.2.解题步骤

第一步，构建维护变量。stack的栈顶维护一个当前层的各个原子个数的哈希表

第二步，遍历表达式。更新维护变量

• 2.1.遇到"("，说明新开一层，压入一个空的哈希表

• 2.2.遇到大写字母，说明遇到一个原子的开头，既要匹配原子符号，也要匹配原子的个数；并将找到的原子个数更新到栈顶哈希表中

• 2.3.如果遇到")"，说明当前层匹配完成，先匹配括号内元素需要乘以的倍数，并更新栈顶哈希表，再将栈顶哈希表和上一层的统计哈希表从栈中弹出并合并，再重新压入栈顶

第三步，从栈中取出最终的统计结果，并按原子名字字典序升序的方式构建原子式字符串

3.解题代码

python3代码

from collections import defaultdict

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        # 思路：栈+哈希表
        n = len(formula)
        # 第一步，构建维护变量。stack的栈顶维护一个当前层的各个原子个数的哈希表
        stack = [defaultdict(int)]
        i = 0
        # 第二步，遍历表达式。更新维护变量
        while i < n:
            ch = formula[i]
            if ch == "(":
                # 2.1.遇到"("，说明新开一层，压入一个空的哈希表
                stack.append(defaultdict(int))
                i += 1
            elif 'A' <= ch <= 'Z':
                # 2.2.遇到大写字母，说明遇到一个原子的开头，既要匹配原子符号，也要匹配原子的个数；并将找到的原子个数更新到栈顶哈希表中
                atom = ch
                i += 1
                # > 匹配原子符号
                while i < n and 'a' <= formula[i] <= 'z':
                    atom += formula[i]
                    i += 1
                # > 匹配原子个数
                cnt = 1
                if i < n and formula[i].isdigit():
                    cnt = int(formula[i])
                    i += 1
                    while i < n and formula[i].isdigit():
                        cnt = cnt * 10 + int(formula[i])
                        i += 1
                stack[-1][atom] += cnt
            elif ch == ")":
                # 2.3.如果遇到")"，说明当前层匹配完成，先匹配括号内元素需要乘以的倍数，并更新栈顶哈希表，再将栈顶哈希表和上一层的统计哈希表从栈中弹出并合并，再重新压入栈顶
                i += 1
                # > 匹配括号后的数值
                cnt = 1
                if i < n and formula[i].isdigit():
                    cnt = int(formula[i])
                    i += 1
                    while i < n and formula[i].isdigit():
                        cnt = cnt * 10 + int(formula[i])
                        i += 1
                # > 更新栈顶，并进行同级合并
                for k, v in stack[-1].items():
                    stack[-1][k] = v * cnt
                newMap = defaultdict(int)
                for _ in range(2):
                    map1 = stack.pop()
                    for k, v in map1.items():
                        newMap[k] += v
                stack.append(newMap)
        # 第三步，从栈中取出最终的统计结果，并按原子名字字典序升序的方式构建原子式字符串
        cnts = stack[-1]
        result = ""
        for k in sorted(cnts.keys()):
            v = cnts[k]
            if v > 1:
                result += k + str(v)
            else:
                result += k
        return result

4.执行结果