11

我想将给定的数学表达式标记为这样的解析树:

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

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

有没有纯 Python 方法来做到这一点?就像作为字符串传递给 Python,然后像上面提到的那样作为树返回。

谢谢。

4

5 回答 5

10

是的,Pythonast模块提供了执行此操作的工具。您必须查找您的 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)))'
于 2011-02-19T07:34:43.860 回答
3

Python 有几个解析器框架。一些常见的是PLYpyparsing。Ned Batchelder 有一个相当完整的清单

于 2011-02-19T07:35:19.483 回答
1

有许多好的、成熟的算法可以解析像这样的数学表达式。一个特别好的方法是 Dijkstra 的shutting-yard algorithm,它可以用来生成这样的树。我不知道 Python 中有一个特定的实现,但该算法并不是特别复杂,并且不应该花费太长时间来启动一个。

顺便说一句,您正在构建的树的更准确术语是解析树抽象语法树

于 2011-02-19T07:30:22.327 回答
1

您可以使用 Python ast 模块执行此操作。

https://docs.python.org/3.6/library/ast.html

该操作是我们要评估的数学运算,我们使用 isinstance 来了解它的类型,如果它是一个数字,如果它是一个二元运算符(+,*,..)。您可以在https://greentreesnakes.readthedocs.io/en/latest/tofrom.html阅读ast 的工作原理

为了使我们可以使用的方法工作:evaluate(ast.parse(theoperation, mode='eval').body)

def evaluate(theoperation): 
    if (isinstance(theoperation, ast.Num)):
        return theoperation.n
    if (isinstance(theoperation, ast.BinOp)):
        leftope= evaluate(theoperation.left)
        rightope=evaluate(theoperation.right)   
        if (isinstance(theoperation.op, ast.Add)):
            return left+right
        elif (isinstance(theoperation.op, ast.Sub)):
            return left-right
        elif (isinstance(theoperation.op, ast.Mult)):
            return left*right
        elif (isinstance(theoperation.op, ast.Div)):
            return left/right
        elif (isinstance(theoperation.op, ast.Pow)):
            return left**right
于 2016-06-16T11:17:22.773 回答
0

我不知道这样做的“纯python”方式,它已经为你实现了。但是,您应该查看 ANTLR (http://www.antlr.org/),它是一个开源解析器和词法分析器,它具有适用于多种语言的 API,包括 python。此外,该网站还有一些很棒的视频教程,将向您展示如何按照您的要求进行操作。这是一个非常有用的工具,可以了解如何使用。

于 2011-02-19T07:31:45.470 回答