在Python中解析表达式树

Question

我有一个遗传程序，它可以把表达式树打印到一个文件里（它可以很方便地在前缀、中缀和后缀之间切换）。

看起来前缀表示法最容易解析，所以我现在在用这个。

我该怎么用Python 2.7来解析这个字符串呢？比如说，如何解析这个字符串 +(*(2,1),*(4,3))，它代表的是 2*1 + 4*3。

f = open('expression_tree.txt', 'r')
input = f.read()
root_node_operator = input[0]

这就是我目前的进展。我对解析不是很熟悉。谢谢！

我有一个Python程序，它打印出表达式树的数据结构，我想在下一个Python程序中解析并计算它。

或者有没有办法把表达式树对象传递给下一个Python程序，这样就不需要解析了？比如我在GP.py里有一个叫 test_tree 的树。我能从我的另一个文件 MyBot.py 访问到它吗？

Answer 1

首先，前缀表示法不需要任何括号，你可以通过字符串中元素的顺序来控制操作的优先级。比如，如果你想表示 2*(1+4)*3，那么你的前缀表达式就会变成 "* * 2 + 1 4 3"。

而 2*1+4*3 则会变成 "+ * 2 1 * 4 3"。使用 split() 方法，这样就能得到一个包含操作符和操作数的列表，像这样：['+', '*', '2', '1', '*', '4', '3']。这个方法会自动跳过空格。接下来要计算这个表达式，就需要递归地遍历这个列表：如果你找到一个操作符，就从当前的位置取出下两个操作数；如果你找到一个常量，就直接返回它。每次从列表中取出一个元素后，记得更新当前的位置。

opns = {
    '+' : lambda a,b: a+b,
    '-' : lambda a,b: a-b,
    '*' : lambda a,b: a*b,
    '/' : lambda a,b: a/b,
    }

def prefix_eval(expr, posn=0):
    # save current element from expression
    current = expr[posn]

    # advance parsing position
    posn += 1

    if current in ['+','-','*','/']:
        # binary operator, get next two operands
        op1,posn = prefix_eval(expr, posn)
        op2,posn = prefix_eval(expr, posn)

        # evaluate operation from current, on operands
        return opns[current](op1,op2), posn
    else:
        # not an operator, must be a numeric value
        return float(current),posn

print prefix_eval("+ * 2 1 * 4 3".split())[0]
print prefix_eval("* * 2 + 1 4 3".split())[0]

打印结果

14.0
30.0

Answer 2

把 +(*(2,1),*(4,3)) 替换成 (+ (* 2 1) (* 4 3))，然后把结果传给 scheme。

$ echo '+(*(2,1),*(4,3))' | sed 's/\(.\)(/(\1 /g; s/,/ /g' | scheme | sed -n '/;Value: /s///p'

如果你想用 python，可以试试 pyparsing 这个库。