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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…