CODEWITHSUNDEEP
pythonparsingmathbinary-treemathematical-expressions
vander
vander

Reputation: 133

Evaluating mathematical expressions in Python

I want to tokenize a given mathematical expression into a parse tree like this:

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

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

Is there any pure Python way to do this? Like passing as a string to Python and then get back as a tree like mentioned above.

Thanks.

Upvotes: 12

Views: 7034

Answers (5)

mich87
mich87

Reputation: 11

You can do this with the Python ast module.

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

theoperation is our mathematical operation we want to evaluate, we use the isinstance in order to know the type it is, if its a number, if its a binary operator(+,*,..). You can read at https://greentreesnakes.readthedocs.io/en/latest/tofrom.html , how the ast work

And in order to make the method work we sould use: 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

Upvotes: 1

Greg Hewgill
Greg Hewgill

Reputation: 993005

Yes, the Python ast module provides facilities to do this. You'll have to look up the exact interface for your version of Python, since the ast module seems to change regularly.

In particular, the ast.parse() method will be helpful for your application:

>>> 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)))'

Upvotes: 10

Nicholas Riley
Nicholas Riley

Reputation: 44321

Several parser frameworks exist for Python; some common ones are PLY and pyparsing. Ned Batchelder has a pretty complete list.

Upvotes: 3

fairidox
fairidox

Reputation: 3428

I don't know of a "pure python" way to do this, that is already implemented for you. However you should check out ANTLR (http://www.antlr.org/) it's an open source parser an lexer and it has an API for a number of languages, including python. Also this website has some great video tutorials that will show you how to do exactly what you are asking. It's a very useful tool to know how to use in general.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372784

There are many good, established algorithms for parsing mathematical expressions like this one. One particularly good one is Dijkstra's shunting-yard algorithm, which can be used to produce such a tree. I don't know of a particular implementation in Python, but the algorithm is not particularly complex and it shouldn't take too long to whip one up.

By the way, the more precise term for the tree you're constructing is a parse tree or abstract syntax tree.

Upvotes: 1

Related Questions