从中创建表达式树时，是否有必要将中缀表示法转换为后缀？

Question

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

Answer 1

不可以。如果您打算构建表达式树，则无需先将表达式转换为后缀。只是在解析时构建表达式树会更简单。

我通常为表达式编写递归下降解析器。在这种情况下，每个递归调用只会返回它解析的子表达式的树。如果你想使用迭代调车场式算法，那么你也可以这样做。

这里是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

请注意，上面的递归下降样式是写了很多分析器的结果。现在我几乎总是用这种方式解析表达式（递归部分，而不是标记化）。它就像表达式解析器一样简单，并且可以轻松处理括号，以及像赋值运算符那样从右向左关联的运算符。