树和树的算法(二)

树的应用：解析树——表达式解析

在完成树数据结构的实现之后，我们现在来看一个如何使用树来解决一些实际问题的示例。在本节中，我们将分析语法树。解析树可用于表示诸如句子或数学表达式之类的真实结构。

如上图所示，树的层次结构有助于我们了解整个表达式的求值顺序。在我们计算顶层乘法之前，我们必须计算子树中的加法和减法。

左子树的加法运算结果为10。右子树的减法运算结果为3。使用树的层次结构，一旦我们计算了表达式中的表达式，我们就可以简单地用一个节点替换整个子树。如此，他将变成下图所示，

下面,我们用树结构来做如下尝试

• 从全括号表达式构建表达式解析树
• 利用表达式解析树对表达式求值
• 从表达式解析树恢复原表达式的字符串形式

首先,全括号表达式要分解为单词Tokens列表。其单词分为括号“()”、操作符“+-*/”和操作数“0~9”这几类。每当我们读到左括号时，我们都会开始一个新的表达式，因此我们应该创建一个新树来对应该表达式。相反，每当我们读到右括号时，我们就完成了一个表达式。我们还知道，操作数将将作为运算符的子节点。最后，我们知道每个运算符都会有一个左子节点和一个右子节点。

综合上面的信息，我们可以定义以下四个规则：

1. 如果当前Token为'('，则添加一个新节点作为当前节点的左子节点，然后下降到该左子节点。
2. 如果当前Token在列表['+','-','/','*']中，则将当前节点的根值设置为该运算符。然后添加一个新节点作为当前节点的右子节点，然后下降到该右子节点。
3. 如果当前Token是数字，则将当前节点的根值设置为该数字，然后返回到父节点。
4. 如果当前Token是')'，则返回到当前节点的父节点。

接下来，我们用全括号表达式:(3+(4*5))作为例子，它分解为单词Tokens表为['(', '3', '+', '(', '4', '*', '5',')', ')']

根据上述规则，创建表达式解析树过程的详细描述如下，

• 创建空树，当前节点为跟节点
• 读入'(',创建了左子节点,当前节点下降
• 读入'3',当前节点根值设置为3,上升到父节点
• 读入'+',当前节点根值设置为+,创建右子节点,当前节点下降
• 读入'(',创建左子节点,当前节点下降
• 读入'4',当前节点设置为4,上升到父节点
• 读入'*',当前节点设置为*,创建右子节点,当前节点下降
• 读入'5',当前节点设置为5,上升到父节点
• 读入')',上升到父节点
• 读入')',再上升到父节点

从上面的步骤，很明显发现，我们需要跟踪当前节点以及当前节点的父节点。树接口为我们提供了一种通过 getLeftChild 和 getRightChild 方法获取节点的子节点的方法，但是我们如何跟踪父节点呢？当我们遍历树时，保持跟踪父对象的简单解决方案是使用栈。每当我们想下降到当前节点的子节点时，我们首先将当前节点入到栈上。当我们想要返回到当前节点的父节点时，我们将父节点从栈中弹出。

接下我们根据以上规则，并使用Stack和BinaryTree类来编写一个Python函数去创建解析树。代码如下，

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 ['+', '-', '*', '/', ')']:
            try:
                currentTree.setRootVal(int(i))
                parent = pStack.pop() # 出栈上升
                currentTree = parent
            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))
        # 操作符
        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree) # 入栈下降
            currentTree = currentTree.getRightChild()
        # 表达式结束
        elif i == ')':
            currentTree = pStack.pop() # 出栈上升

    return eTree

随后，为了计算出表达式的值，我们实现evaluate函数。代码如下，

import operator
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()

求值函数evaluate的递归三要素:

• 基本结束条件:叶节点是最简单的子树,没有左右子节点,其根节点的据项即为子表达式树的值。
• 缩小规模:将表达式树分为左子树、右子树,即为缩小规模。
• 调用自身:分别调用evaluate计算左子树和右子树的值,然后将左右子树的值依根节点的操作符进行计算,从而得到表达式的值。

至此，已经设计完成解析树，并可以实现对解析式的求值，下面我们测试一下，完整代码如下，

# 栈
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)


# 二叉树类
class BinaryTree:
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    # 插入左子节点
    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    # 插入右子节点
    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    # 获取左子节点
    def getLeftChild(self):
        return self.leftChild

    # 获取右子节点
    def getRightChild(self):
        return self.rightChild

    # 设置子节点携带的值
    def setRootVal(self, obj):
        self.key = obj

    # 获取节点携带的值
    def getRootVal(self):
        return self.key


import operator
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()


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 ['+', '-', '*', '/', ')']:
            try:
                currentTree.setRootVal(int(i))
                parent = pStack.pop()  # 出栈上升
                currentTree = parent
            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))
        # 操作符
        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)  # 入栈下降
            currentTree = currentTree.getRightChild()
        # 表达式结束
        elif i == ')':
            currentTree = pStack.pop()  # 出栈上升

    return eTree

# 测试
pt = buildParseTree("( ( 10 + 5 ) * 3 )")
print(evaluate(pt))

# 输出 45