分析树可以用于表示诸如句子或数学表达式的真实世界构造。
在本节的其余部分，我们将更详细地检查分析树。 特别的，我们会看
如何从完全括号的数学表达式构建分析树。如何评估存储在分析树中的表达式。如何从分析树中恢复原始数学表达式。
我们知道，每当我们读一个左括号，我们开始一个新的表达式，因此我们应该创建一个新的树来对应于该表达式。 相反，每当我们读一个右括号，我们就完成了一个表达式。 我们还知道操作数将是叶节点和它们的操作符的子节点。 最后，我们知道每个操作符都将有一个左和右孩子。
使用上面的信息，我们可以定义四个规则如下：
如果当前符号是 ‘(‘，添加一个新节点作为当前节点的左子节点，并下降到左子节点。
如果当前符号在列表 [‘+’，’ - ‘，’/’，’*’] 中，请将当前节点的根值设置为由当前符号表示的运算符。 添加一个新节点作为当前节点的右子节点，并下降到右子节点。
如果当前符号是数字，请将当前节点的根值设置为该数字并返回到父节点。
如果当前符号是 ‘)’，则转到当前节点的父节点。
我们将使用表达式（3+（4 * 5））。 我们将把这个表达式解析成下面的字符标记列表['('，'3'，'+'，'('，'4'，'*'，'5'，')'，')']。 最初，我们将使用由空根节点组成的分析树开始。
# -*- coding:utf-8 -*- import operator 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 is None: self.leftChild = BinaryTree(newNode) else: t = BinaryTree(newNode) t.leftChild = self.leftChild self.leftChild = t def insertRight(self, newNode): if self.rightChild is 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 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 == ')': currentTree = pStack.pop() elif i in ['+', '-', '*', '/']: currentTree.setRootVal(i) currentTree.insertRight('') pStack.push(currentTree) currentTree = currentTree.getRightChild() elif i not in ['+', '-', '*', '/']: currentTree.setRootVal(int(i)) parent = pStack.pop() currentTree = parent else: raise ValueError return eTree 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() pt = buildParseTree("( ( 10 + 5 ) * 3 )") print(evaluate(pt))