python - 在 Python 中解析化学公式

Question

我正在尝试解决这个问题: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

但现在我卡住了。

随着编码问题变得越来越长，并且涉及到要解决的数据结构的混合，我有点卡住了。这里他们使用哈希表和堆栈。

所以我的问题是:如何将这个问题分解成可管理的部分并加以解决。如果我真的要解决这个问题，我必须将它映射到可管理的代码段。任何帮助将不胜感激。

谢谢。

Answer 1

我认为你可以使用递归来解决这个问题。以下是您的函数应如何工作:

• 像在第一个代码中那样做，直到遇到左括号。
• 遇到左括号时，找到对应的右括号。这可以用一个计数器来完成:将它初始化为 1，然后当你遇到一个新的左括号时，你递增计数器，当你遇到一个右括号时，你递减它。当计数器等于 0 时，您已找到匹配的右括号。
• 截断括号之间的字符串并使用该字符串调用相同的函数(这是递归方面)。
• 将返回字典中的值与当前字典相加，乘以括号后面的数字。

如果您在实现此解决方案的某些部分时遇到问题，请告诉我，我会提供更多详细信息。

编辑:关于堆栈方法 堆栈方法只是模拟递归。它没有再次调用该函数并拥有本地计数器，而是拥有一堆计数器。当左括号打开时，它在此上下文中计数，当它关闭时，它将它与包含它的上下文合并，并具有相应的多重性。

到目前为止，我更喜欢递归方法，它更自然。