我将尝试解决这个问题:https://leetcode.com/articles/number-of-atoms/#approach-1-recursion-accepted。这个问题是:给定一个类似于
C(Mg2(OH)4)2
的公式,返回一个元素和它们数量的哈希表。元素名称总是以大写字母开头,后面可能跟着一个小写字母。我认为我首先要解决最简单的情况:没有括号。def bracket_hash(formula):
element = ""
atom_count = 0
element_hash = {}
for x in formula:
if x.isupper():
if element!="":
element_hash[element] = 1
element = ""
element = x
elif x.islower():
element += x
else:
element_count = int(x)
element_hash[element] = element_count
element_count = 0
element = ""
if element!="":
element_hash[element] = 1
return element_hash
这段代码在以下情况下运行得非常好:
print(bracket_hash("H2O"))
print(bracket_hash("CO2"))
print(bracket_hash("Mg2O4"))
print(bracket_hash("OH"))
我认为在处理像OH(Ag3(OH)2)4
这样有多个括号的情况时,可能需要使用堆栈。在这个例子中,Ag的数量必须是3*4,而O和H的数量将是2*4 + 1。
到目前为止,我的起点类似于以下内容:
def formula_hash(formula):
stack = []
final_hash = {}
cur = ""
i = 0
while i < len(formula):
if formula[i] == '(':
j = i
while formula[j]!=')':
j = j + 1
cur = formula[i:j]
stack.append(bracket_hash(cur))
cur = ""
i = j + 1
但现在我卡住了。
当编码问题变得更长且需要使用多种数据结构来解决时,我会陷入困境。在这里,他们使用哈希表和栈。
所以我的问题是:如何将这个问题分解成可管理的部分并解决它。如果我真的要解决这个问题,我必须将其映射到可管理的代码段中。任何帮助都将不胜感激。
谢谢。