python数据结构与算法 38 分析树

分析树

树的结构完成以后,该是时候看看它能做点什么实事儿了。这一节里,我们研究一下分析树。分析树能够用于真实世界的结构表示,象语法或数学表达式一类的。

python数据结构与算法 38 分析树

1 一个简单语句的分析树


1所示是一个简单语句的层级结构,把语句表示为树结构可以让我们用子树来分析句子的组成部分。

python数据结构与算法 38 分析树

2 ((7+3)?(5?2))的分析树

我们也可以把数学表达式如((7+3)?(5?2))表示为分析树,如图2.此前我们研究过完全括号表达式,这个表达式表达了什么呢?我们知道乘法的优先级比加减要高,但因为括号的关系,在做乘法之前,要先完成加减法的计算。树的层级结构能帮助我们理解整个表达式的计算顺序。左子树是加法,求值得10,减法是右子树,求值得3.因为树的层级结构,可以用求得的值代替左右子树,这样就可以直接计算乘法了。

python数据结构与算法 38 分析树

3 ((7+3)?(5?2))的简化分析树

本章其余部分我们研究分析树的更多细节,特别是要研究:

  • 对完全括号表达式怎样构建分析树。
  • 怎样对分析树的表达式求值
  • 怎样从分析树还原数学表达式。

构建分析树,第一步是把表达式分解成符号保存在列表里。这里面有4种符号:左括号,右括号,操作符,操作数。我们知道每当读到一个左括号,就是新开一个表达式,这时就要新建一个子树来对应括号内的表达式。相反地,每读到一个右括号,这个子表达式就结束了。另外我们也要知道,操作数总是操作符的叶子。最后我们要知道,每个操作符都有左右两个孩子。

知道了以上信息,我们可以给出以下规则:

1.   如果当前符号是’(‘,新增一个节点作为当前节点的左孩子,并下沉到这个左孩子。

2.   如果当前符号在  [‘+‘,‘-‘,‘/‘,‘*‘],把当前节点的值赋为当前符号,并且为当前节点增加一个右孩子,并下沉到这个右孩子。

3.   如果当前符号是一个数字,把当前节点值设为这个数,返回到父母节点。

4.   如果当前符号是‘)’,返回到父母节点。

开始写代码之前,我们先看一看上面的规则是怎样运作的。以表达式 (3+(4?5))为例,我们把它分析成字符列表[‘(‘, ‘3‘, ‘+‘, ‘(‘, ‘4‘, ‘*‘, ‘5‘,‘)‘,‘)‘].,我们从一个只含有空根节点的分析树开始,如图4所示为结构,和每一次操作后的内容。

python数据结构与算法 38 分析树

新建空节点


python数据结构与算法 38 分析树

读到左括号,规则1

python数据结构与算法 38 分析树

读到3,规则3

python数据结构与算法 38 分析树

读到+,规则2


python数据结构与算法 38 分析树

读到左括号,规则1

python数据结构与算法 38 分析树

读到数字4,规则3

python数据结构与算法 38 分析树

读到*,规则2

python数据结构与算法 38 分析树

读到数字5,规则3

4 跟踪分析树构建


按图4,步骤是这样的的:

  1. 建一个空树
  2. 读入第一个符号(,按规则1,新建一个节点作为根的左孩子。把左孩子作为当前节点。
  3. 读入第二个符号3,按规则3,将节点值设为3,并返回到它的父母。
  4. 读入第三个符号+,按规则2,将节点值设为+并增加右孩子,并作为当前节点
  5. 读入第四个符号(,按规则1,新建一个节点,作为当前节点的左孩子,并设为当前节点
  6. 读入第五个符号4,按规则3,节点值设为4,将它的父母作为当前节点。
  7. 读入下一个符号*,按规则2,当前节点值设为*并新建一个右节点。新节点设为当前节点。
  8. 读入下一个符号5,按规则3,当前节点值设为5,它的父母作为当前节点。
  9. 读入下一个符号),按规则4,*的父母成为当前节点
  10. 读入下一个符号),按规则4,+的父母作为当前节点。+没有父母,操作结束。

从上面的例子很清楚地看到,我们必须保持对“当前节点”和它的“父母节点”的跟踪。树的接口已经提供了获得孩子节点的方法,getLeftChild  getRightChild  但是怎样跟踪父母呢?一个简单方法就是使用栈,每当下沉到当前节点的孩子时,先把当前节点压栈,当要返回到当前节点的父母时,从栈中弹出。

使用以上规则,加上 Stack  BinaryTree 的操作,现在我们可以写分析树的代码了。如下:


from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree

def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree(‘‘)
    pStack.push(eTree)
    currentTree = eTree
    for i in fplist:
        if i == ‘(‘:
            currentTree.insertLeft(‘‘)
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i not in [‘+‘, ‘-‘, ‘*‘, ‘/‘, ‘)‘]:
            currentTree.setRootVal(int(i))
            parent = pStack.pop()
            currentTree = parent
        elif i in [‘+‘, ‘-‘, ‘*‘, ‘/‘]:
            currentTree.setRootVal(i)
            currentTree.insertRight(‘‘)
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()
        elif i == ‘)‘:
            currentTree = pStack.pop()
        else:
            raise ValueError
    return eTree

pt = buildParseTree("( ( 10 + 5 ) * 3 )")
pt.postorder()  #下节讲到


上面代码中,我们讲过的四规则,分别体现在if语句的四个分枝中,即11151924行。在每种情况下,都可以看到规则的实现,包括几次对 BinaryTree  Stack 的调用。唯一的错误检查在else 子句中,升起一个 ValueError 异常,应对从列表中得到一个不能识别的字符的情况。

现在分析树已经建起来了,怎样用呢?作为第一个例子,我们写一个函数来求分析树的值,返回计算结果。写这个函数要用到树的层级结构,回头看看图2记得我们用图3中的简化树代替了原来的树,这提示我们写一个递归算法对子树求值。

以前我们做过递归算法了,这次我们从设计递归的基点开始。树的自然基点是叶子。在分析树中,叶子节点总是操作数,象整数或浮点数之类的数字对象不需要更多操作,所以 evaluate 函数可以直接返回它的值。递归走向基点的的方法是对左右孩子使用 evaluate 函数。

要把两个递归调用的结果合在一起,只需要简单地对这两个结果应用存在父母节点的操作符,在图3的例子中,我们可以看到两个孩子自己求值,各得103,对他们应用乘法,得到最终结果30

递归函数 evaluate linsting 1。首先,要得到左右孩子的引用,如果左右孩子都是None,那么当前节点是叶子。这个检查过程在第7行。如果不是叶子,查找当前节点的操作符,并用到它左右孩子的返回值上。

在算法中,使用了字典数据类型,其中键值是 ‘+‘, ‘-‘, ‘*‘ ‘/‘。数值部分是pythonoperator模块的函数。Operator模块提供了常用操作符的函数版,这样当我们查找操作符的时候,返回相应的函数。既然是函数,我们可以用函数方式来计算算式。比如我们查找 opers[‘+‘](2,2) ,等价于operator.add(2,2).

Listing 1

def evaluate(parseTree):
    opers = {‘+‘:operator.add, ‘-‘:operator.sub, ‘*‘:operator.mul, ‘/‘:operator.truediv}

    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()

    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootVal()

最后,我们用图4中的例子来跟踪求值函数evaluate  。当调用evaluate,,我们把一整个子树作为参数传递过去。然后我们得到左右子树的引用以确认他们是存在的。递归调用发生在第9行,开始查找根节点的操作符,这里是 ‘+‘,它对应的函数是operator.add ,需要两个参数。象一般的python函数一样,它要做的第一件事情就是计算两个参数的函数值。在本例中,两个参数都是对 evaluate 的递归调用。从左到右求值,第一个递归函数得到了左子树,发现这个节点没有孩子,所以是叶子。在叶子节点上,仅仅返回它的数值就可以,这里返回了整数3

此时我们的*调用 operator.add的一个参数已经算出来了,但还没完。继续从左到右的求值,现在求右子树的值,发现它有左右孩子,根值是*,再对它的两个孩子调用函数,这时发现它的左右孩子是叶子,分别返回两个整数45,用这两个参数计算operator.mul(4,5)。这时,*调用+的左右子树已经计算出来,这时要计算 operator.add(3,20)。最终的结果是23.





python数据结构与算法 38 分析树,布布扣,bubuko.com

python数据结构与算法 38 分析树

上一篇:线程、内存、锁定和阻塞(Threads, Memory, Locking, and Blocking)


下一篇:菜鸟调错(四)——Spring与DWR集成,配置文件报错