在Python中评估数学表达式

Question

我想把一个数学表达式分解成一个解析树，像这样：

((3 + 4 - 1) * 5 + 6 * -7) / 2

                          '/'
                        /     \
                       +        2
                    /     \
                  *         *
                /   \     /   \
               -     5   6     -7
             /   \
            +     1
          /   \
         3     4

有没有什么纯Python的方法可以做到这一点？比如把表达式作为字符串传给Python，然后得到上面提到的那种树形结构。

谢谢。

Answer 1

有很多不错的算法可以用来解析像这样的数学表达式。其中一个特别好的算法是戴克斯特拉的切换算法，它可以用来生成这样的树。虽然我不知道在Python中有没有具体的实现，但这个算法其实并不复杂，自己写一个也不会花太长时间。

顺便提一下，你正在构建的树的更准确的名称是解析树或者抽象语法树。

Answer 2

Python有很多解析器框架，常见的有PLY和pyparsing。Ned Batchelder还整理了一个相当完整的列表。

Answer 3

是的，Python 的 ast 模块可以帮助你实现这个功能。你需要查一下你所用的 Python 版本对应的具体接口，因为 ast 模块似乎会经常更新。

特别是，ast.parse() 方法对你的应用会很有帮助：

>>> import ast
>>> ast.parse("(1+2)*3", "", "eval")
<_ast.Expression object at 0x88950>
>>> ast.dump(_)
'Expression(body=BinOp(left=BinOp(left=Num(n=1), op=Add(), right=Num(n=2)), op=Mult(), right=Num(n=3)))'