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

Question

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: / * ^ + -.

Answer 1

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.