实验五二叉树的应用表达式求值.docx

实验五二叉树的应用表达式求值.docx

《实验五二叉树的应用表达式求值.docx》由会员分享，可在线阅读，更多相关《实验五二叉树的应用表达式求值.docx（15页珍藏版）》请在冰点文库上搜索。

实验五二叉树的应用表达式求值

浙江大学城市学院实验报告

课程名称python高级程序设计

实验项目名称实验五二叉树的应用----表达式求值

实验成绩指导老师（签名）日期

一.实验目的和要求

1、掌握二叉树的链式存储结构；

2、掌握在二叉链表上的二叉树的基本操作；

3、掌握二叉树的简单应用----表达式树的操作。

二.实验内容

1、在实验四中，已经实现了对一个中缀表达式可以用栈转换成后缀表达式，并可对后缀表达式进行求值计算的方法。

另一种思路是可以利用二叉树建立表达式树，通过对该表达式树进行求值计算，本实验实现：

输入一个中缀表达式，建立该表达式的二叉树，然后对该二叉树进行表达式值的计算。

如一个中缀达式（6+2）*5的二叉树表示为如下所示时，该二叉树的后序遍历62+5*正好就是后缀表达式。

设一般数学表达式的运算符包括+、-、*、/四种，当然允许（），且（）优先级高。

为方便实现，设定输入的表达式只允许个位整数。

要求设计一个完整的程序，对输入的一个日常的中缀表达式，实现以下功能：

⏹建立对应的二叉树

⏹输出该二叉树的前序序列、中序序列、后序序列

⏹求该二叉树的高度

⏹求该二叉树的结点总数

⏹求该二叉树的叶子结点数

⏹计算该二叉树的表达式值

分析：

（1）表达式树的构建方法：

●构建表达式树的方法之一：

直接根据输入的中缀表达式构建

对于任意一个算术中缀表达式，都可用二叉树来表示。

表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。

因此问题的关键就是如何创建表达式树。

对于一个中缀表达式来说，其表达式对应的表达式树中叶子结点均为操作数，分支结点均为运算符。

由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。

这种处理方式在实验四中以采用过，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。

根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。

可以另外借助一个表达式树栈，来暂存已建立好的表达式树的根结点，以便其作为另一个运算符结点的子树而被引用。

为实现表达式树的创建算法，可以使用两个工作栈，一个称为OPTR，用以暂存运算符；另一个称为EXPT，用以暂存已建立好的表达式树子树的根结点。

为了便于实现，假设每个表达式均以“#”开始，以“#”结束，如输入“（6+2）*5#”。

表达式树的创建算法过程如下：

1初始化OPTR和EXPT，将表达式起始符“#”压入OPTR栈

2扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR栈顶不为“#”时，则循环执行以下操作：

●若ch不是运算符，则以ch为根创建一棵只有根结点的二叉树，且将该树根结点压入EXPT栈，读入下一个ch；

●若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同处理：

Ø小于，则ch压入OPTR栈，读入下一个ch；

Ø大于，则弹出OPTR栈顶运算符，从EXPT栈弹出两个表达式子树的根结点，以该运算符为根结点，以弹出的第二个子树作为左子树，弹出的第一个子树为右子树，创建一棵新二叉树，并将该树根结点压入EXPT栈；

Ø相等，则OPTR的栈顶元素是“（”且ch是“）”，这时弹出OPTR栈顶的“（”，相当于括号匹配成功，然后读入下一个ch。

●构建表达式树的方法之二：

直接根据转换后的后缀表达式构建

实验四中已经实现把一个中缀表达式转换成为后缀表达式，则可以在此转换后的后缀表达式基础上构建表达式树，可以省略了前面方法中关于运算符优先级的比较过程，可以直接构建，方法类似于前面方法。

（2）表达式树的求值：

对于构建完成的表达式树，通过中序遍历即可方便求得表达式的值。

1设变量lvalue和rvalue分别用以记录表达式树中左子树和右子树的值，初始均为0。

2如果当前结点为叶子（结点为操作数），则返回该结点的数值，否则（结点为运算符）执行以下操作：

●递归计算左子树的值记为lvalue；

●递归计算右子树的值记为rvalue；

●根据当前结点运算符的类型，将lvalue和rvalue进行相应运算并返回。

请仔细阅读上述内容，编程实现输入一个中缀表达式，采用任意一种方法构建表达式树，并完成表达式的计算。

为方便约定了初始操作数均个位整数，运算符只包括+、-、*、/种，中间运算结果也均为整数。

此外可自行增加合适的功能，可作为额外的实验成绩进行加分，如：

●操作数扩展到大于个位的整数。

●操作数扩展到浮点数

●操作数扩展到负数

●添加其他运算符

……

2、以小组为单位认真填写实验报告，实验报告可包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。

同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。

3、实验报告文件取名为表达式求值_（各小组成员名字）.doc。

每组还必须制作一个答辩PPT，PPT的命名为PPT_表达式求值_（各小组成员名字）.PPT。

实验报告以及PPT同时作为实验成绩一部分。

4、每位组长上传实验报告文件、源程序文件以及答辩PPT压缩打包后到BB平台上。

5、允许参考其他相应的设计原理方法等，但拒绝复制，一经发现，整小组本次实验成绩计0分处理。

3、实验结果与总结

（1）小组分工

郑博思：

建立对应的二叉树、输出该二叉树的前序序列、中序序列、后序序列、ppt制作

郑超：

求该二叉树的高度、计算该二叉树的表达式值、ppt制作

徐慧：

求该二叉树的结点总数、求该二叉树的叶子结点数、分析实验报告

（二）代码分析如下：

classtree:

def__init__（self）:

self.data=0

self.left=None

self.right=None

分析：

中序遍历子程序：

二叉树不为空，遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

definorder（ptr）:

ifptr!

=None:

inorder（ptr.left）

print（ptr.data,'',end=''）

inorder（ptr.right）

分析：

前序遍历子程序：

二叉树不为空，首先访问根结点然后遍历左子树，最后遍历右子树。

在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

defpreorder（ptr）:

ifptr!

=None:

print（ptr.data,'',end=''）

preorder（ptr.left）

preorder（ptr.right）

分析：

后序遍历子程序：

首先遍历左子树，然后遍历右子树，最后访问根结点。

defpostorder（ptr）:

ifptr!

=None:

postorder（ptr.left）

postorder（ptr.right）

print（ptr.data,'',end=''）

分析：

求二叉树的结点总数：

如果是空树则为0，如果不是计算根节点左子树与根节点右子树，再将左子树节点个数+右子树节点个数+根节点个数1=即为整颗树的节点个数。

defnodecount（ptr）:

ifptr==None:

return0

else:

returnnodecount（ptr.left）+nodecount（ptr.right）+1

分析：

递归求叶子节点个数：

如果是空树，叶子节点为0，返回0；左、右子树均不为空，则是叶子节点，且叶子节点数为1，返回1根节点的子树叶子节点数=左子树叶子节点数+T右子树叶子节点数。

defleave（ptr）:

ifptr==None:

return0

elifptr.lchild==Noneandptr.rchild==None:

return1

else:

return（self.leave（ptr.lchild）+self.leave（ptr.rchild））

分析：

求二叉树的深度：

若不为空树，m为左子树的深度，n为右子树的深度，取两者最大在加上一个根结点。

defTreeDepth（ptr）:

ifptr==None:

return0

else:

m=TreeDepth（ptr.left）

n=TreeDepth（ptr.right）

returnmax（m,n）+1

分析：

建立二叉树的函数

defcreate_tree（root,val）:

newnode=tree（）

newnode.data=val

newnode.left=None

newnode.right=None

ifroot==None:

root=newnode

returnroot

else:

current=root

whilecurrent!

=None:

backup=current

ifcurrent.data>val:

current=current.left

else:

current=current.right

ifbackup.data>val:

backup.left=newnode

else:

backup.right=newnode

returnroot

分析：

设置主程序，以data建立二叉查找树

data=[5,6,24,8,12,3,17,1,9]

print（'===以下按照data值',data,'构建二叉查找树==='）

ptr=None

foriinrange（9）:

ptr=create_tree（ptr,data[i]）

分析：

输出结果

print（'中序遍历的结果：

',end=''）

inorder（ptr）#中序遍历

print（''）

print（'前序遍历的结果：

',end=''）

preorder（ptr）

print（''）

print（'后序遍历的结果：

',end=''）

postorder（ptr）

print（''）

print（'二叉树深度为：

',end=''）

postorder（ptr）

print（''）

print（'二叉树叶子节点数为：

',end=''）

k=TreeDepth（ptr）

print（k）

print（'二叉树结点总数为：

',end=''）

k=nodecount（ptr）

print（k）

分析：

以下输入表达式，建立表达式树

#栈的设置

classmystack:

def__init__（self）:

self.stack=[]

self.top=-1

self.maxstack=100

分析：

判断是否为空堆栈

defisEmpty（s）:

ifs.top==-1:

returnTrue

else:

returnFalse

分析：

判断是否已满

defisFull（s）:

ifs.top>=s.maxstack-1:

returnTrue

else:

returnFalse

分析：

将指定的数据压入堆栈

defpush（s,data）:

ifisFull（s）:

print（'堆栈已满,无法再加入'）

else:

s.top+=1

s.stack[s.top]=data#将数据压入堆栈

分析：

从堆栈弹出数据

defpop（s）:

ifisEmpty（s）:

print（'堆栈为空！

pop失败！

'）

else:

e=s.stack[s.top]

s.top=s.top-1

returne

defgettop（s）:

ifisEmpty（s）:

print（'堆栈为空！

peek失败'）

else:

returns.stack[s.top]

分析：

运算符优先级比较

op=['#','+','-','*','/','（','）']#允许的运算符

opdata=[0,2,2,3,3,4,1]#赋值用于优先级比较

definop（ch）:

#判断是否是运算符

globalop

foriinrange（len（op））:

ifop[i]==ch:

returnTrue

returnFalse

分析：

判断运算符ch1、ch2的优先级

defcompare（ch1,ch2）:

s="+-*/（）#"

tab=[">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=I",">>>>I>>","<<<<

i=s.find（ch1）

j=s.find（ch2）

returntab[i][j]

defnewnode（nodedata,nodeleft,noderight）:

newp=tree（）

newp.data=nodedata

newp.left=nodeleft

newp.right=noderight

returnnewp

分析：

创建表达式树

defExpTree（exp）:

root=None

optr=mystack（）

optr.stack=[None]*optr.maxstack

expt=mystack（）

expt.stack=[None]*expt.maxstack

分析：

把‘#’压入运算符栈底，作为结束标记

push（optr,'#'）

分析：

表达式字符串长度

explen=len（exp）

i=0

ch=exp[i]

while（ch!

='#'orgettop（optr）!

='#'）:

ifinop（ch）==False:

t=newnode（int（ch）,None,None）

push（expt,t）

i=i+1

else:

ch0=gettop（optr）

k=compare（ch0,ch）

ifk=='=':

pop（optr）

i=i+1

elifk=='<':

push（optr,ch）

i=i+1

else:

#k=='>'

b=pop（expt）

a=pop（expt）

t=newnode（pop（optr）,a,b）

push（expt,t）

ch=exp[i]

root=pop（expt）

ifgettop（optr）=='#'andisEmpty（expt）:

print（"表达式正确！

表达式树构建完成，根指针为root！

"）

returnroot

else:

print（"表达式输入错误！

表达式树构建失败！

"）

returnNone

分析：

计算achb的结果

defGetValue（a,ch,b）:

ifch=='+':

result=int（a）+int（b）

elifch=='-':

result=a-b

elifch=='*':

result=a*b

elifch=='/':

result=int（a）//int（b）

returnresult

分析：

#遍历表达式树进行求值

defEvaluateExpTree（root）:

lvalue=rvalue=0

ifroot.left==Noneandroot.right==None:

returnint（root.data）

分析：

#递归求左子树、右子树的值rvalue，计算lvalueT->datarvalue

else:

lvalue=EvaluateExpTree（root.left）

rvalue=EvaluateExpTree（root.right）

value=GetValue（lvalue,root.data,rvalue）

returnvalue

#exp=input（'inputanexpression:

'）

exp="2*（4+3）*2-（6-2）/2#"

print（'===以下按照字符串',exp,'构建表达式树并求值==='）

root=ExpTree（exp）

print（'表达式树中序遍历：

',end=''）

inorder（root）

print（''）

print（'表达式树前序遍历：

',end=''）

preorder（root）

print（''）

print（'表达式树后序遍历：

',end=''）

postorder（root）

print（''）

print（'表达式的值为：

',end=''）

print（EvaluateExpTree（root））

（三）运行结果

（4）小组总结

本来应该在上次实验的基础上将中缀表达式转成对树的建立以及深度与节点数的计算，但是由于我们水平不足无法在之前的代码上进行增添修改。

因此本次实验主要参考了书上的代码和老师的例子。

写入叶子节点数稍微研究了一下，在经过几次错误也终于可以运行成功。

我们认为参考课本对我们的本次实验给予了很大的帮助，也在理解上面更好接受，但是我们深知自己的水平有限，所以会继续努力。