Оценка математических выражений в Python

Я хочу токенизировать данное математическое выражение в дереве синтаксического анализа следующим образом:

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

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

Есть ли способ сделать это на чистом Python? Это как передача Python в виде строки, а затем возврат в виде дерева, как указано выше.

Спасибо.


python parsing math binary-tree mathematical-expressions
person vander    schedule 19.02.2011    source источник

Ответы (5)


arrow_upward
10
arrow_downward

Да, модуль 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)))'
person Greg Hewgill    schedule 19.02.2011

arrow_upward
3
arrow_downward

Для Python существует несколько фреймворков парсеров; наиболее распространенными из них являются PLY и pyparsing. У Неда Батчелдера есть довольно полный список.

person Nicholas Riley    schedule 19.02.2011
comment
Лепл - другой - acooke.org/lepl - и как написать синтаксический анализатор для подобных выражений (и оценить полученный AST) подробно рассматривается в руководстве - acooke.org/lepl /intro-4.html#evaluation [отказ от ответственности: я являюсь автором] - person andrew cooke; 19.02.2011

arrow_upward
1
arrow_downward

Есть много хороших, устоявшихся алгоритмов для анализа математических выражений, подобных этому. Один из особенно хороших - это маневровый алгоритм Дейкстры, который можно использовать для создания такого дерево. Я не знаю конкретной реализации на Python, но алгоритм не особенно сложен, и его разработка не займет много времени.

Кстати, более точный термин для дерева, которое вы строите, - это дерево синтаксического анализа или абстрактное синтаксическое дерево.

person templatetypedef    schedule 19.02.2011

arrow_upward
1
arrow_downward

Вы можете сделать это с помощью модуля Python ast.

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

theoperation - это наша математическая операция, которую мы хотим оценить, мы используем isinstance, чтобы узнать, какой это тип, если это число, если это бинарный оператор (+, *, ..). Вы можете прочитать на https://greentreesnakes.readthedocs.io/en/latest/tofrom.html, как работает Ast

И чтобы заставить этот метод работать, мы могли бы использовать: Assessment (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
person mich87    schedule 16.06.2016

arrow_upward
0
arrow_downward

Я не знаю способа сделать это на "чистом питоне", который уже реализован для вас. Однако вы должны проверить ANTLR (http://www.antlr.org/), это анализатор с открытым исходным кодом, лексер и API для ряда языков, включая Python. Также на этом веб-сайте есть несколько отличных видеоуроков, которые покажут вам, как делать именно то, что вы просите. Это очень полезный инструмент, который нужно знать в целом.

person fairidox    schedule 19.02.2011