用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

此代码适用于以下情况：

^{pr2}$

现在我想应该用堆栈来处理多个方括号的情况，比如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

您可能需要搜索python parser generator。解析器生成器是一个库，可以帮助开发人员为任何类型的公式或语言（技术上是任何“语法”）创建解析器，而无需从头开始做所有工作。在

你可能需要读一些书来理解化学式所遵循的语法类型。在

Python的一个有趣的概述是this。在

Answer 2

我想你可以用递归来解决这个问题。以下是您的函数应该如何工作：

• 像在第一个代码中那样做，直到遇到一个左括号。在
• 当遇到左括号时，找到相应的右括号。这可以用一个计数器来完成：将其初始化为1，然后当遇到新的左括号时，将计数器递增，当遇到右括号时，则将其递减。当计数器等于0时，您找到了匹配的右括号。在
• 切掉括号之间的字符串，并用这个字符串调用同一个函数（这是递归方面）。在
• 将返回字典中的值乘以括号后的数字，将返回的字典中的值加到当前字典中。在

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

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

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