在Python中解析化学式

Question

在Python中解析化学式

3

我将尝试解决这个问题：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

但现在我卡住了。

当编码问题变得更长且需要使用多种数据结构来解决时，我会陷入困境。在这里，他们使用哈希表和栈。

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

谢谢。

- mourinho

2个回答

1

你可能需要谷歌一下python parser generator。一个解析器生成器是一个库，它帮助开发者创建任何类型的公式或语言（技术上来说，任何“语法”）的解析器，而不必从头开始做所有工作。

您可能需要阅读一些内容才能了解化学式遵循的语法类型。

对于Python，有一个有趣的概述this。

- DCS

3

他们提出问题的目的不是为了完成任务，而是学习如何执行算法。 - nyr1o

即便如此，研究最新技术也是一个好主意。解析并不是一件简单的事情。 - DCS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nyr1o · Accepted Answer

我认为您可以使用递归来解决这个问题。以下是函数的工作方式：

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

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

编辑：有关堆栈方法

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

我远远更喜欢递归方法，因为它更自然。