Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
817 views
in Technique[技术] by (71.8m points)

data structures - Is it necessary to convert infix notation to postfix when creating an expression tree from it?

I want to create an expression tree given expression in infix form. Is it necessary to convert the expression to postfix first and then create the tree? I understand that it somehow depends on the problem itself. But assume that it is simple expression of mathematical function with unknowns and operators like: / * ^ + -.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

No. If you're going to build an expression tree, then it's not necessary to convert the expression to postfix first. It will be simpler just to build the expression tree as you parse.

I usually write recursive descent parsers for expressions. In that case each recursive call just returns the tree for the subexpression that it parses. If you want to use an iterative shunting-yard-like algorithm, then you can do that too.

Here's a simple recursive descent parser in python that makes a tree with tuples for nodes:

import re

def toTree(infixStr):
    # divide string into tokens, and reverse so I can get them in order with pop()
    tokens = re.split(r' *([+-*^/]) *', infixStr)
    tokens = [t for t in reversed(tokens) if t!='']
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2}

    #convert infix expression tokens to a tree, processing only
    #operators above a given precedence
    def toTree2(tokens, minprec):
        node = tokens.pop()
        while len(tokens)>0:
            prec = precs[tokens[-1]]
            if prec<minprec:
                break
            op=tokens.pop()

            # get the argument on the operator's right
            # this will go to the end, or stop at an operator
            # with precedence <= prec
            arg2 = toTree2(tokens,prec+1)
            node = (op, node, arg2)
        return node

    return toTree2(tokens,0)

print toTree("5+3*4^2+1")

This prints:

('+', ('+', '5', ('*', '3', ('^', '4', '2'))), '1')

Try it here:

https://ideone.com/RyusvI

Note that the above recursive descent style is the result of having written many parsers. Now I pretty much always parse expressions in this way (the recursive part, not the tokenization). It is just about as simple as an expression parser can be, and it makes it easy to handle parentheses, and operators that associate right-to-left like the assignment operator.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...