一、题目：原子的数量
给定一个化学式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只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。
思路：时间O（n)，空间O（n)
采用一个栈，存储数字
从后往前遍历： for s in formula[::-1]
（1）遇到数字，则令 num = 数字* (10^i )，【存在连续两个数字出现，如“Be32”】故采用 i 来判断，如果前面一个字母不是数字，则 i = 0， 否则，i+=1。
即 if s.isdigit():
num += int(s)*(10**i)
i += 1
（2）遇到 '）'，则将 num数字加入栈 stack 中，因为数字存在两种情况，【如‘H4（CO3）2’，像3和4是不用存到栈中，2要存进stack中】，故遇到 ）才将num存进stack中。然后令num=0，i=0
即 if s == ')':
stack.append(num)
num = i = 0
（3）遇到‘（’，则将栈最后一个元素删除，因为【‘H2（CO3（CaO)4）2’】，此时stack中应该为【4，2】，遇到第一个（将2弹出，因为CO3对应的系数应为2，而CaO对应的系数为4*2=8。
即 if s == '(':
stack.pop()
num = i = 0
（4）大写字母，则将完整字母，【‘Mg'】存入字典中，其对应的系数为栈中所有数相乘的结果，如果字典中原来存在的话就将原来的系数加上，
其余条件初始化：num = i = 0，string = ’‘【小写字母】，count = 1【栈中所有的数相乘结果】
即 if s.isupper():
string += s count = num if num else 1 #像【‘H2（CO3（CaO)4）2’】count=3，再与栈中所有数相乘#栈中所有数相乘
for m in stack: count *= m
# 将结果存入字典中 if string[::-1] in dic: dic[string[::-1]] += count else: dic[string[::-1]] = count
#初始化 string = '' count,num,i= 1,0,0
（5）小写字母，与之前的字母相加起来
即 if s.islower():
string += s
代码：
def countOfAtoms(self, formula): """ :type formula: str :rtype: str """ if not formula: return "" stack = [] dic = {} string = '' count,num,i = 1,0,0 for s in formula[::-1]: if s.isdigit(): num += int(s)*(10**i) i+=1 elif s == ')': stack.append(num) num = 0 i=0 elif s == '(': stack.pop() i ,num= 0,0 elif s.isupper(): string += s count = num if num else 1 for m in stack: count *= m if string[::-1] in dic: dic[string[::-1]] += count else: dic[string[::-1]] = count string = '' count,num = 1,0 i = 0 elif s.islower(): string += s sort = sorted(dic.items(),key = lambda x:x[0]) res = '' for item in sort: res += item[0] if item[1]>1: res += str(item[1]) return res