分析树
树的结构完成以后，该是时候看看它能做点什么实事儿了。这一节里，我们研究一下分析树。分析树能够用于真实世界的结构表示，象语法或数学表达式一类的。
图1 一个简单语句的分析树
图1所示是一个简单语句的层级结构，把语句表示为树结构可以让我们用子树来分析句子的组成部分。
图2 ((7+3)?(5?2))的分析树
我们也可以把数学表达式如((7+3)?(5?2))表示为分析树，如图2.此前我们研究过完全括号表达式，这个表达式表达了什么呢？我们知道乘法的优先级比加减要高，但因为括号的关系，在做乘法之前，要先完成加减法的计算。树的层级结构能帮助我们理解整个表达式的计算顺序。左子树是加法，求值得10，减法是右子树，求值得3.因为树的层级结构，可以用求得的值代替左右子树，这样就可以直接计算乘法了。
图3 ((7+3)?(5?2))的简化分析树
本章其余部分我们研究分析树的更多细节，特别是要研究：
- 对完全括号表达式怎样构建分析树。
- 怎样对分析树的表达式求值
- 怎样从分析树还原数学表达式。
构建分析树，第一步是把表达式分解成符号保存在列表里。这里面有4种符号：左括号，右括号，操作符，操作数。我们知道每当读到一个左括号，就是新开一个表达式，这时就要新建一个子树来对应括号内的表达式。相反地，每读到一个右括号，这个子表达式就结束了。另外我们也要知道，操作数总是操作符的叶子。最后我们要知道，每个操作符都有左右两个孩子。
知道了以上信息，我们可以给出以下规则：
1. 如果当前符号是’(‘，新增一个节点作为当前节点的左孩子，并下沉到这个左孩子。
2. 如果当前符号在 [‘+‘,‘-‘,‘/‘,‘*‘],把当前节点的值赋为当前符号，并且为当前节点增加一个右孩子，并下沉到这个右孩子。
3. 如果当前符号是一个数字，把当前节点值设为这个数，返回到父母节点。
4. 如果当前符号是‘）’,返回到父母节点。
开始写代码之前，我们先看一看上面的规则是怎样运作的。以表达式 (3+(4?5))为例，我们把它分析成字符列表[‘(‘, ‘3‘, ‘+‘, ‘(‘, ‘4‘, ‘*‘, ‘5‘,‘)‘,‘)‘].，我们从一个只含有空根节点的分析树开始，如图4所示为结构，和每一次操作后的内容。
新建空节点
读到左括号，规则1
读到3，规则3
读到+，规则2
读到左括号，规则1
读到数字4，规则3
读到*，规则2
读到数字5，规则3
图4 跟踪分析树构建
按图4，步骤是这样的的：
- 建一个空树
- 读入第一个符号（，按规则1，新建一个节点作为根的左孩子。把左孩子作为当前节点。
- 读入第二个符号3，按规则3，将节点值设为3，并返回到它的父母。
- 读入第三个符号+，按规则2，将节点值设为+并增加右孩子，并作为当前节点
- 读入第四个符号（，按规则1，新建一个节点，作为当前节点的左孩子，并设为当前节点
- 读入第五个符号4，按规则3，节点值设为4，将它的父母作为当前节点。
- 读入下一个符号*，按规则2，当前节点值设为*并新建一个右节点。新节点设为当前节点。
- 读入下一个符号5，按规则3，当前节点值设为5，它的父母作为当前节点。
- 读入下一个符号），按规则4，*的父母成为当前节点
- 读入下一个符号），按规则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语句的四个分枝中，即11，15，19和24行。在每种情况下，都可以看到规则的实现，包括几次对 BinaryTree 或 Stack 的调用。唯一的错误检查在else 子句中，升起一个 ValueError 异常，应对从列表中得到一个不能识别的字符的情况。
现在分析树已经建起来了，怎样用呢？作为第一个例子，我们写一个函数来求分析树的值，返回计算结果。写这个函数要用到树的层级结构，回头看看图2记得我们用图3中的简化树代替了原来的树，这提示我们写一个递归算法对子树求值。
以前我们做过递归算法了，这次我们从设计递归的基点开始。树的自然基点是叶子。在分析树中，叶子节点总是操作数，象整数或浮点数之类的数字对象不需要更多操作，所以 evaluate 函数可以直接返回它的值。递归走向基点的的方法是对左右孩子使用 evaluate 函数。
要把两个递归调用的结果合在一起，只需要简单地对这两个结果应用存在父母节点的操作符，在图3的例子中，我们可以看到两个孩子自己求值，各得10和3，对他们应用乘法，得到最终结果30
递归函数 evaluate 见linsting 1。首先，要得到左右孩子的引用，如果左右孩子都是None，那么当前节点是叶子。这个检查过程在第7行。如果不是叶子，查找当前节点的操作符，并用到它左右孩子的返回值上。
在算法中，使用了字典数据类型，其中键值是 ‘+‘, ‘-‘, ‘*‘和 ‘/‘。数值部分是python中operator模块的函数。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的一个参数已经算出来了，但还没完。继续从左到右的求值，现在求右子树的值，发现它有左右孩子，根值是*，再对它的两个孩子调用函数，这时发现它的左右孩子是叶子，分别返回两个整数4和5，用这两个参数计算operator.mul(4,5)。这时，*调用+的左右子树已经计算出来，这时要计算 operator.add(3,20)。最终的结果是23.