从中缀符号创建表达式树时是否需要将中缀符号转换为后缀？
Is it necessary to convert infix notation to postfix when creating an expression tree from it?
我想创建一个表达式树，给定中缀形式的表达式。是否需要先将表达式转换为后缀，然后再创建树？我知道这在某种程度上取决于问题本身。但假设它是带有未知数和运算符的数学函数的简单表达式，例如：/ * ^ + -.
没有。如果您要构建表达式树，则不必先将表达式转换为后缀。在解析时构建表达式树会更简单。
我通常为表达式编写递归下降解析器。在那种情况下，每个递归调用只是 returns 它解析的子表达式的树。如果您想使用类似调车场的迭代算法，那么您也可以这样做。
这是 python 中的一个简单的递归下降解析器，它为节点创建一个包含元组的树：
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")
这会打印：
('+', ('+', '5', ('*', '3', ('^', '4', '2'))), '1')
在这里试试：
注意上面的递归下降风格是写了很多解析器的结果。现在我几乎总是以这种方式解析表达式（递归部分，而不是标记化）。它与表达式解析器一样简单，并且可以轻松处理括号和从右到左关联的运算符（如赋值运算符）。
我想创建一个表达式树，给定中缀形式的表达式。是否需要先将表达式转换为后缀，然后再创建树？我知道这在某种程度上取决于问题本身。但假设它是带有未知数和运算符的数学函数的简单表达式，例如：/ * ^ + -.
没有。如果您要构建表达式树，则不必先将表达式转换为后缀。在解析时构建表达式树会更简单。
我通常为表达式编写递归下降解析器。在那种情况下，每个递归调用只是 returns 它解析的子表达式的树。如果您想使用类似调车场的迭代算法，那么您也可以这样做。
这是 python 中的一个简单的递归下降解析器，它为节点创建一个包含元组的树：
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")
这会打印：
('+', ('+', '5', ('*', '3', ('^', '4', '2'))), '1')
在这里试试：
注意上面的递归下降风格是写了很多解析器的结果。现在我几乎总是以这种方式解析表达式（递归部分，而不是标记化）。它与表达式解析器一样简单，并且可以轻松处理括号和从右到左关联的运算符（如赋值运算符）。