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

问题描述

我想以中缀形式创建一个给定表达式的表达式树.是否需要先将表达式转换为后缀，然后再创建树?我知道这在某种程度上取决于问题本身.但假设它是带有未知数和运算符的数学函数的简单表达，例如:/* ^ + -.

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

推荐答案

没有.如果要构建表达式树，则无需先将表达式转换为后缀.在解析时构建表达式树会更简单.

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.

这是一个简单的 Python 递归下降解析器，它创建了一个带有节点元组的树:

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")

打印:

('+', ('+', '5', ('*', '3', ('^', '4', '2'))), '1')

在这里试试:

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.

这篇关于从中创建表达式树时是否有必要将中缀表示法转换为后缀?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！