从其创建表达树时，是否有必要将infix符号转换为后缀

Question

我想以infix形式创建一个表达式树。是否有必要先将表达式转换为Postfix然后创建树？我了解这在某种程度上取决于问题本身。但是，假设它是数学函数的简单表达，而未知数和运算符，例如：/* ^ - 。

Answer 1

no。如果要构建一个表达式树，则无需先将表达式转换为Postfix。仅在解析时构建表达树就会更简单。

我通常为表达式编写递归血统解析器。在这种情况下，每个递归调用只会返回树的解析的子表达。如果您想使用迭代分流码状算法，那么您也可以做到。

这是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'）

在这里尝试：

https://ideone.com/ryusvi

请注意，上述递归下降样式是写了许多解析器的结果。现在，我几乎总是以这种方式解析表达（递归部分，而不是令牌化）。它几乎和表达式解析器一样简单，并且使处理括号很容易，并且运算符将左右左右关联的操作员像分配运算符一样。