解析树
完成树的实现之后，现在我们来看一个例子，告诉你怎么样利用树去解决一些实际问题。在这个章节，我们来研究解析树。解析树常常用于真实世界的结构表示，例如句子或数学表达式。
图 1：一个简单句的解析树
图 1 显示了一个简单句的层级结构。将一个句子表示为一个树，能使我们通过利用子树来处理句子中的每个独立的结构。
图 2： ((7+3)*(5−2)) 的解析树
如图 2 所示，我们能将一个类似于 ((7+3)*(5−2)) 的数学表达式表示出一个解析树。我们已经研究过全括号表达式，那么我们怎样理解这个表达式呢？我们知道乘法比加或者减有着更高的优先级。因为括号的关系，我们在做乘法运算之前，需要先计算括号内的加法或者减法。树的层级结构帮我们理解了整个表达式的运算顺序。在计算最顶上的乘法运算前，我们先要计算子树中的加法和减法运算。左子树的加法运算结果为 10，右子树的减法运算结果为 3。利用树的层级结构，一旦我们计算出了子节点中表达式的结果，我们能够将整个子树用一个节点来替换。运用这个替换步骤，我们得到一个简单的树，如图 3 所示。
图 3： ((7+3)*(5−2)) 的化简后的解析树
在本章的其余部分，我们将更加详细地研究解析树。尤其是：
怎样根据一个全括号数学表达式来建立其对应的解析树
怎样计算解析树中数学表达式的值
怎样根据一个解析树还原数学表达式
建立解析树的第一步，将表达式字符串分解成符号保存在列表里。这里有四种符号需要我们考虑：左括号，操作符和操作数。我们知道读到一个左括号时，我们将开始一个新的表达式，因此我们创建一个子树来对应这个新的表达式。相反，每当我们读到一个右括号，我们就得结束这个表达式。另外，操作数将成为叶节点和他们所属的操作符的子节点。最后，我们知道每个操作符都应该有一个左子节点和一个右子节点。通过上面的分析我们定义以下四条规则：
如果当前读入的字符是'('，添加一个新的节点作为当前节点的左子节点，并下降到左子节点处。
如果当前读入的字符在列表['+', '-', '/', '*']中，将当前节点的根值设置为当前读入的字符。添加一个新的节点作为当前节点的右子节点，并下降到右子节点处。
如果当前读入的字符是一个数字，将当前节点的根值设置为该数字，并返回到它的父节点。
如果当前读入的字符是')'，返回当前节点的父节点。
在我们编写 Python 代码之前，让我们一起看一个上述的例子。我们将使用 (3+(4*5))
这个表达式。我们将表达式分解为如下的字符列表：['(', '3', '+', '(', '4', '*', '5' ,')',')']。一开始，我们从一个仅包括一个空的根节点的解析树开始。如图 4，该图说明了随着每个新的字符被读入后该解析树的内容和结构。
图 4：解析树结构的步骤图
观察图 4，让我们一步一步地过一遍：
- 创建一个空的树。
- 读如(作为第一个字符，根据规则 1，创建一个新的节点作为当前节点的左子结点，并将当前节点变为这个新的子节点。
- 读入3作为下一个字符。根据规则 3，将当前节点的根值赋值为3然后返回当前节点的父节点。
- 读入+作为下一个字符。根据规则 2，将当前节点的根值赋值为+，然后添加一个新的节点作为其右子节点，并且将当前节点变为这个新的子节点。
- 读入(作为下一个字符。根据规则 1，创建一个新的节点作为当前节点的左子结点，并将当前节点变为这个新的子节点。
- 读入4作为下一个字符。根据规则 3，将当前节点的根值赋值为4然后返回当前节点的父节点
- 读入*作为下一个字符。根据规则 2，将当前节点的根值赋值为*，然后添加一个新的节点作为其右子节点，并且将当前节点变为这个新的子节点。
- 读入5作为下一个字符。根据规则 3，将当前节点的根值赋值为5然后返回当前节点的父节点
- 读入)作为下一个字符。根据规则 4，我们将当前节点变为当前节点*的父节点。
- 读入)作为下一个字符。根据规则 4，我们将当前节点变为当前节点+的父节点，因为当前节点没有父节点，所以我们已经完成解析树的构建。
通过上面给出的例子，很明显我们需要跟踪当前节点和当前节点的父节点。树提供给我们一个获得子节点的方法——通过getLeftChild和getRightChild方法，但是我们怎么样来跟踪一个节点的父节点呢？一个简单的方法就是在我们遍历整个树的过程中利用栈跟踪父节点。当我们想要下降到当前节点的子节点时，我们先将当前节点压入栈。当我们想要返回当前节点的父节点时，我们从栈中弹出该父节点。
通过上述的规则，使用栈和二叉树来操作，我们现在编写函数来创建解析树。解析树生成函数的代码如下所示。
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() #defined and explained in the next section
</div>
这四条建立解析树的规则体现在四个if从句，它们分别在第 11,15,19,24 行。如上面所说的，在这几处你都能看到规则的代码实现，并需要调用一些BinaryTree和Stack的方法。这个函数中唯一的错误检查是在else语句中，一旦我们从列表中读入的字符不能辨认，我们就会报一个ValueError的异常。现在我们已经建立了一个解析树，我们能用它来干什么呢？第一个例子，我们写一个函数来计算解析树的值，并返回该计算的数字结果。为了实现这个函数要利用树的层级结构。重新看一下图 2，回想一下我们能够将原始的树替换为简化后的树（图 3）。这提示我们写一个通过递归计算每个子树的值来计算整个解析树的值。
就像我们以前实现递归算法那样，我们将从基点来设计递归计算表达式值的函数。这个递归算法的自然基点是检查操作符是否为叶节点。在解析树中，叶节点总是操作数。因为数字变量如整数和浮点数不需要更多的操作，这个求值函数只需要简单地返回叶节点中存储的数字就可以。使函数走向基点的递归过程就是调用求值函数计算当前节点的左子树、右子树的值。递归调用使我们朝着叶节点，沿着树下降。
为了将两个递归调用的值整合在一起，我们只需简单地将存在父节点中的操作符应用到两个子节点返回的结果。在图 3 中，我们能看到两个子节点的值，分别为 10 和 3。对他们使用乘法运算得到最终结果 30。
递归求值函数的代码如 Listing1 所示，我们得到当前节点的左子节点、右子节点的参数。如果左右子节点的值都是 None，我们就能知道这个当前节点是一个叶节点。这个检查在第 7 行。如果当前节点不是一个叶节点，查找当前节点的操作符，并用到它左右孩子的返回值上。
为了实现这个算法，我们使用了字典，键值分别为'+'，'-'，'*'和'/'。存在字典里的值是 Python 的操作数模块中的函数。这个操作数模块为我们提供了很多常用函数的操作符。当我们在字典中查找一个操作符时，相应的操作数变量被取回。既然是函数，我们可以通过调用函数的方式来计算算式，如function(param1,param2)。所以查找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 pars