文章作者：Tyan 博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
解析：这道题还有优化的空间，这样写主要是逻辑清晰。1. 把元素(多个字母)、数字(多个数字字符)、左右括号拆分开；2. 计算元素的个数，如果元素后没有数字，则添加数字1作为元素个数；当碰到右括号时，查找其对应的左括号，并将其中的元素个数乘以括号后的数字，其后没数字，则默认乘以1；3. 统计元素个数，相同元素个数相加；4. 排序字典，按元素字母排序；5. 构造返回结果字符串。
- Version 1
class Solution:
def countOfAtoms(self, formula):
stat = {}
stack = []
parts = []
# Split string by alpha, number, '(', ')'
for index, ch in enumerate(formula):
if ch.isupper():
parts.append(ch)
elif ch.islower():
parts[-1] = ch
elif ch.isdigit():
if formula[index - 1].isdigit():
parts[-1] = ch
else:
parts.append(ch)
else:
parts.append(ch)
# Calculate the number of atom and remove '(', ')'
stack = []
for index, part in enumerate(parts):
if part.isalpha():
if index 1 == len(parts) or not parts[index 1].isdigit():
stack.append(part)
stack.append(1)
else:
stack.append(part)
elif part.isdigit() and parts[index - 1] != ')':
stack.append(int(part))
elif part == '(':
stack.append(part)
elif part == ')':
if index 1 < len(parts) and parts[index 1].isdigit():
multiplier = int(parts[index 1])
else:
multiplier = 1
i = len(stack) - 1
while stack[i] != '(':
if isinstance(stack[i], int):
stack[i] = stack[i] * multiplier
i -= 1
stack.pop(i)
# Stat the number of atoms
for i in range(0, len(stack), 2):
if stack[i] in stat:
stat[stack[i]] = stack[i 1]
else:
stat[stack[i]] = stack[i 1]
stat = sorted(stat.items(), key=lambda item: item[0])
result = ''
for key, value in stat:
if value > 1:
result = result key str(value)
else:
result = result key
return resultReference
- https://leetcode.com/problems/number-of-atoms/
