树的应用:表达式解析
-
可以将表达式表示为树结构:叶节点保存操作数,内部节点保存操作符
-
全括号表达式((7+3)(5-2))
由于括号的存在,需要计算的话,就必须先计算7+3和5‐2,表达式层次决定计算的优先级
越底层的表达式,优先级越高
3.树中每个子树都表示一个子表达式:将子树替换为子表达式值的节点,即可实现求值
- 下面,我们用树结构来做如下尝试
- 从全括号表达式构建表达式解析树
- 利用表达式解析树对表达式求值
- 从表达式解析树恢复原表达式的字符串形式
- 首先,全括号表达式要分解为单词列表
- 其单词分为括号“ () ” 、操作符“ +‐*/” 和操作数“ 0~ 9” 这几类
- 左括号就是表达式的开始,而右括号是表达式的结束
建立表达式解析树:实例
- 创建表达式解析树的四个原则
- 如果当前标记是( ,就为当前节点添加一个左子节点,并下沉至该子节点;
- 如果当前标记在列表 [’+’ , ‘-’ , ‘/’ , ‘*’ ] 中,就将当前节点的值设为当前标记对应的运算符;为当前节点添加一个右子节点,并下沉至该子节点;
- 如果当前标记是数字,就将当前节点的值设为这个数并返回至父节点;
- 如果当前标记是) ,就跳到当前节点的父节点。
- 建立表达式解析树:实例 全括号表达式: (3+(4*5))
- 分解为单词表 [’(’, ‘3’, ‘+’, ‘(’, ‘4’, ‘*’, ‘5’, ‘)’, ‘)’]
- 创建空树,当前节点为根节点
- 读入’(’, 创建了左子节点,当前节点下降
- 读入’3’,当前节点设置为3, 上升到父节点
- 读入’+’,当前节点设置为+, 创建右子节点,当前节点下降
- 读入’(’, 创建左子节点,当前节点下降
- 读入’4’,当前节点设置为4, 上升到父节点
- 读入’’,当前节点设置为, 创建右子节点,当前节点下降
- 读入’5’,当前节点设置为5, 上升到父节点
- 读入’)’, 上升到父节点
- 读入’)’,再上升到父节点
- 建立表达式解析树:思路
-
从图示过程中我们看到,创建树过程中关键的是对当前节点的跟踪
- 创建左右子树可调用insertLeft/Right
- 当前节点设置值,可以调用setRootVal
- 下降到左右子树可调用getLeft/RightChild
- 但是, 上升到父节点,这个没有方法支持!
-
我们可以用一个栈来记录跟踪父节点
- 当前节点下降时,将下降前的节点push入栈
- 当前节点需要上升到父节点时,上升到pop出栈的节点即可!
-
创建了表达式解析树,可用来进行求值
-
由于二叉树BinaryTree是一个递归数据结构,自然可以用递归算法来处理
-
求值递归函数evaluate:由前述对子表达式的描述,可从树的底层子树开始,逐步向上层求值,最终得到整个表达式的值
-
求值函数evaluate的递归三要素:
- 基本结束条件:叶节点是最简单的子树,没有左右子节点,其根节点的数据项即为子表达式树的值
- 缩小规模:将表达式树分为左子树、右子树,即为缩小规模
- 调用自身:分别调用evaluate计算左子树和右子树的值,然后将左右子树的值依根节点的操作符进行计算,从而得到表达式的值
# 栈
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(0, item)
def pop(self):
return self.items. pop(0)
def peek(self):
return self.items[0]
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 getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
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 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
# 利用表达式解析树求值
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() # 基本结束条件