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}。
提示：
1<=formula.length<=1000
formula由英文字母、数字、'('和')'组成
formula总是有效的化学式
问题分析及解决思路：
为了使问题处理更加简便，对化学式中原子符号是两个或两个以上字母的，用原子符号大写字母之后的第一个小写字母进行替换，这样简化成每一个原子都只用一个字母代表，在处理完成之后，再替换回原来的原子符号
刚开始，我认为只要对原始字符串formula一层层去括号，括号去完之后，再将数字转换为相应数量的原子字符，最后再统计各原子的数量，整理得到题目要求的结果。比如形如(AB)2(CD(EF)2)2(CD)2这样的化学式，其处理步骤如下：
(AB)2(CD(EF)2)2(CD)2--->ABABCD(EF)2CD(EF)2CDCD---->ABABCDEFEFCDEFEFCDCD--->统计各原子个数--->A2B2C4D4E4F4
结果发现把最外层的括号一次性全部去掉的处理使问题变得较为复杂
其实，可以使处理更加简便单纯，每次只处理第一个括号，处理完成后再处理新生成的字符串的第一个括号，直到字符串中没有括号为止。比如上面的化学式，可以这样处理：
(AB)2(CD(EF)2)2(CD)2--->ABAB(CD(EF)2)2(CD)2--->ABABCD(EF)2CD(EF)2(CD)2--->ABABCDEFEFCD(EF)2(CD)2--->ABABCDEFEFCDEFEF(CD)2--->ABABCDEFEFCDEFEFCDCD--->统计各原子个数--->A2B2C4D4E4F4
其实，这种简化处理印证了一种思维，函数功能尽量简单单纯，不要复杂，这样使程序的可读性变强，处理思路更加清晰，功能更加容易实现，正如python之禅所说：Simple is better than complex.
根据上面的处理思路，设计了如下一些函数来处理：
- 函数fposition(s)，功能是对字符串s，寻找第一个括号的起始位置和结束位置的索引号，并返回
- 函数getnum(s,end)，功能是根据字符串s中括号的结束位置end，找到其后所跟数字并返回，如果没有数字或括号的结束位置已经处于s的结尾，则返回1
- 函数clyc(s)，功能是对字符串s找到第一个括号的起始位置和结束位置，并根据结束位置找到其后的数字，将数字作用于括号中的字符处理的结果字符串返回
- 函数nposition(s)，功能为查找字符串s中数字出现的索引号，如果没有数字，返回0，这个函数配合getnum(s,end)函数，是在将字符串中的括号处理完之后，只剩下字母和数字的情况下使用的
- 函数lastcl(s)，功能是对已经处理完括号的字符串s进行数字的反复处理，返回一个没有数字的字符串
- 函数find2atom(s)，功能将原子符号是两个或两以上的找出，并以列表形式返回
程序如下：
#在字符串s中找到第一个括号的起始位置和对应的结束位置并返回
def fposition(s):
n=len(s)
k=0
start=0
end=0
for i in range(n):
if s[i]=='(':
if k==0:
start=i
k=k+1
elif s[i]==')':
k=k-1
if k==0:
end=i
break
return start,end
#在字符串s中根据右括号的位置end找到在其右的数字并返回，如果没有数字或已经处于s的结尾，返回1
def getnum(s,end):
n=len(s)
if end==n-1 or end<n-1 and not s[end+1].isnumeric():
return 1
else:
for i in range(end+1,n):
if s[i].isnumeric():
continue
else:
return int(s[end+1:i])
else:
return int(s[end+1:])
#对字符串s根据括号和其后的数字进行一次处理，并返回处理之后的字符串
def clyc(s):
n=len(s)
start,end=fposition(s)
num=getnum(s,end)
s1=s[:start]
s2=s[start+1:end]*num
k=end+len(str(num))
if k==n-1:
s3=''
else:
s3=s[k+1:]
return s1+s2+s3
#返回字符串s中第一个数字的位置，如果没有数字，返回0
def nposithon(s):
n=len(s)
for i in range(n):
if s[i].isnumeric():
return i
else:
return 0
#对已经处理完括号的字符串s按其中的数字反复处理，返回一个没有数字的字符串
def lastcl(s):
i=nposithon(s)
while i!=0:
n = getnum(s, i-1)
s1=s[:i-1]
s2=s[i-1]*n
s3=s[i+len(str(n)):]
s=s1+s2+s3
i=nposithon(s)
return s
#查找并返回字符串s中含有两个或两个以上字母的原子
def find2atom(s):
a=[]
n=len(s)
k=0
start=0
for i in range(n):
if s[i].islower():
if k==0:
start=i-1
k=k+1
else:
if k!=0:
a.append(s[start:i])
start=0
k=0
else:
continue
if k!=0:
a.append(s[start:])
return a
#主程序
formula=input('pls input formula=')
#查找formula中包含两个或两个以上字母的原子
a=find2atom(formula)
# 对formula中有两个或两个以上字母的原子用该原子的第一个小写字母替换
for i in a:
formula=formula.replace(i,i[1])
#去掉所有括号
while '(' in formula:
formula=clyc(formula)
#处理数字，变成无数字字符的字符串
s=lastcl(formula)
#统计各字符的个数并按字典顺序重新合成新的字符串
d=list(set(list(s)))
e=[]
for i in d:
c=s.count(i)
e.append([i,str(c) if c>1 else ''])
#将替换为小写字母的原子替换回原来多个字母形式的原子符号
for i in e:
for j in a:
if i[0]==j[1]:
i[0]=j
#按字典序排序
e.sort(key=lambda x:x[0])
#组合成最终结果并输出
s=''.join(list(map(lambda x:''.join(x),e)))
print(s)运行实例一
pls input formula=Mg(OH)2
H2MgO2
运行实例二
pls input formula=(AB)2(CD(EF)2)2(CD)2
A2B2C4D4E4F4
运行实例三
pls input formula=K4(ON(SO3)2)2
K4N2O14S4
运行实例四
pls input formula=Aggg3(Cu(OH)2)2(NaOH)2
Aggg3Cu2H6Na2O6
感悟：
编程犹如雕刻，雕刻用雕刀雕出精美的艺术品，独具匠心，编程则用编程语言和算法思想对问题抽丝剥茧，可谓匠心独运。要提高技艺，都需要反复练习，或心细如发，或大巧若拙，熟能生巧，方能形成智慧的结晶。
![[STM32]从零开始的STM32 HAL库环境搭建](https://i-blog.csdnimg.cn/direct/a7a398c253614eb9b2d46eadced3a417.png)
