递归解析 LXML 树并避免重复进入某个节点

1、问题背景

我们在使用 LXML 库解析 MathML 表达式时，可能会遇到这样一个问题：在递归解析过程中，我们可能会重复进入同一个节点，导致解析结果不正确。例如，我们希望将以下 MathML 表达式解析为 Python 表达式：

<?xml version="1.0"?>
<math xmlns="http://www.w3.org/1998/Math/MathML" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.w3.org/1998/Math/MathML http://www.w3.org/Math/XMLSchema/mathml2/mathml2.xsd">
  <mrow>
    <mfrac>
      <mn>3</mn>
      </mn>
      <mn>5</mn>
      </mn>
    </mfrac>
  </mrow>
</math>
1
2
3
4
5
6
7
8
9
10
11

如果我们使用以下代码来解析该表达式：

def parseMML(mmlinput):
    from lxml import etree
    from StringIO import *
    from lxml import objectify
    exppy=[]
    events = ("start", "end")
    context = etree.iterparse(StringIO(mmlinput),events=events)
    for action, elem in context:
        if (action=='start') and (elem.tag=='mrow'):
            exppy+='('
        if (action=='end') and (elem.tag=='mrow'):
            exppy+=')'
        if (action=='start') and (elem.tag=='mfrac'):
            mmlaux=etree.tostring(elem[0])
            exppy+=parseMML(mmlaux)
            exppy+='/'
            mmlaux=etree.tostring(elem[1])
            exppy+=parseMML(mmlaux)
        if action=='start' and elem.tag=='mn': #this is a number
            exppy+=elem.text
    return (exppy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

那么我们得到的解析结果将是：

['(', '(', '3', ')', '/', '(', '5', ')', '(', '3', ')', '(', '5', ')', ')']
1

而不是我们期望的：

['(', '(', '3', ')', '/', '(', '5', ')', ')']
1

这是因为在解析 mfrac 节点时，我们递归调用了 parseMML 函数两次，分别解析了分子和分母。而在解析分子时，我们又递归调用了 parseMML 函数，导致重复进入了 mrow 节点。

2、解决方案

为了解决这个问题，我们可以使用一个栈来保存已经解析过的节点。当我们开始解析一个新的节点时，我们可以将该节点压入栈中。当我们完成解析该节点时，我们可以将该节点从栈中弹出。这样，我们就能够避免重复进入同一个节点。

以下代码演示了如何使用栈来避免重复进入同一个节点：

def parseMML(mmlinput):
    from lxml import etree
    from StringIO import *
    from lxml import objectify
    exppy=[]
    events = ("start", "end")
    context = etree.iterparse(StringIO(mmlinput),events=events)
    nodestack=[]
    for action, elem in context:
        if action=='start' and elem.tag in nodestack:
            continue
        if (action=='start') and (elem.tag=='mrow'):
            nodestack.append(elem.tag)
            exppy+='('
        if (action=='end') and (elem.tag=='mrow'):
            nodestack.pop()
            exppy+=')'
        if (action=='start') and (elem.tag=='mfrac'):
            nodestack.append(elem.tag)
            mmlaux=etree.tostring(elem[0])
            exppy+=parseMML(mmlaux)
            exppy+='/'
            mmlaux=etree.tostring(elem[1])
            exppy+=parseMML(mmlaux)
        if action=='start' and elem.tag=='mn': #this is a number
            exppy+=elem.text
    return (exppy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

使用该代码，我们可以得到正确的解析结果：

['(', '(', '3', ')', '/', '(', '5', ')', ')']
1