表达式类型的实现

..**理工大学数据结构课程设计报告题目： 表达式类型的实现 院〔系： 计算机工程学院 学生姓名: ** __计算111学号: 2011070** 起迄日期:——2012.7.19 指导教师: *** 一、需求分析1.问题描述：本程序通过输入前缀表达式建立一颗二叉树,通过中序遍历建立好的二叉树输出带括号的中缀表达式。然后中序遍历二叉树对表达式中的未知数x进行赋值。通过后序遍历二叉树计算表达式的值。根据两颗二叉树和输入的运算符构造复合表达式。另外,通过中序遍历二叉树对表达式进行化简。2.基本功能⑴以字符序列的形式输入语法正确的前缀表示式并构成表达式E⑵用带括号的中缀表达式输出表达式E⑶实现对变量x的赋值,变量初始值为0⑷对算术表达式求值⑸构造新的复合表达式〔E1P〔E2⑹对表达式进行化简3.输入输出本程序运算数的输入输出局限于无符号整型数据,运算符的输入输出包括"+、-、*、/、^"二、概要设计1.设计思路：本程序以字符序列的形式输入语法正确的前缀表达式,在输入表达式的过程中判断输入的字符是运算数还是运算符并将其保存到树节点中相应的位置,表达式输入结束的同时也就构成一颗二叉树。根据建立好的二叉树,可以采用中序遍历二叉树的方法输出正常顺序的表达式。在中序遍历二叉树时,访问存放运算符的结点时要判断其与双亲结点中运算符的优先级关系来判断是否要添加括号。在给表达式中的未知数x赋值时,本程序采用的是中序遍历二叉树的方法,遇到存放x的结点就将数值赋值给其数据域的变量。然后通过后序遍历二叉树的方法就行表达式求值。构造复合表达式可以分别建立两颗二叉树,然后将这两颗二叉树作为新申请的运算符结点的左右孩子结点。在化简表达式时,先判断运算符结点的两个孩子节点是不是运算数结点〔不包括x结点。如果两个孩子节点是运算数结点,就计算出这个子表达式的值并用其代替这个运算符结点。2.数据结构设计：抽象数据类型二叉树的定义如下：ADTBinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=φ,则R=φ,称BinaryTree为空二叉树；若D≠φ,则R={H},H是如下二元关系：〔1在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；〔2若D-{root}≠φ,则存在D_{root}={D1,Dr},且D1∩Dr=φ；〔3若D1≠φ,则D1中存在唯一的元素X1,<root,X1>∈H,且存在 D1上的关系H1∈H；若Dr≠φ,则Dr中存在唯一的元素Xr,<root,Xr> ∈H,且存在Dr上的关系Hr∈H；H={<root,X1>,<root,Xr>,H1,Hr}；〔4〔D1,{H1}是一颗符合本定义的二叉树,称为根的左子树,〔Dr,{Hr} 是一颗符合本定义的二叉树,称为根的右子树。基本操作：CreatBitTree<BitTreeT,BitTreep>;操作结果：根据前缀表达式先序构造二叉树。InOrderTraverse<BitTreeT>初始条件：二叉树T存在。操作结果：中序遍历二叉树T,输出每个结点的数据域且仅一次。InOrder<BitTreeT,int*num>;初始条件：二叉树T存在且存在x结点。操作结果：将num赋值给x。PostOrderTraverse<BitTreeT>;初始条件：二叉树T。操作结果：后序遍历二叉树求表达式的值。}ADTBinaryTree3.软件结构设计：BitTreeReadExpr<BitTreeT>;BitTreeReadExpr<BitTreeT>;BitTreeWriteExpr<BitTreeT>BitTreeWriteExpr<BitTreeT>BitTreeAssign<BitTreeT>;BitTreeAssign<BitTreeT>;BitTreeValue<BitTreeT>;BitTreeValue<BitTreeT>;Intmain〔Voidmenu〔Intmain〔Voidmenu〔voidCompoundExpr<BitTreeT>;voidCompoundExpr<BitTreeT>;voidMergeConstruction<BitTreeT>;voidMergeConstruction<BitTreeT>;退出！退出！三、详细设计定义程序中所有用到的数据及其数据结构,及其基本操作的实现；typedefstructBitNode{ chardata; intopnd; structBitNode*lchild; structBitNode*rchild; structBitNode*parent;}BitNode,*BitTree;2．主函数和其他函数的伪码算法；<1>主函数：intmain<>{ BitTreeT=NULL; T=<BitTree>malloc<sizeof<BitNode>>; if<T==NULL> {printf<"有错\n">;} else { flag=0; menu<T>; } return0;}菜单函数：voidmenu<BitTreeT>{ intsel=0; do { printf<"\n\n">; printf<"<1>以字符序列的形式输入语法正确的前缀表示式并构造表达式\n">; printf<"<2>用带括弧的中缀表达式输出表达式\n">; printf<"<3>实现对变量x的赋值〔x=c,变量的初值为0\n">; printf<"<4>对算术表达式求值\n">; printf<"<5>造一个新的复合表达式〔E1P<E2>\n">; printf<"<6>表达式化简\n">; printf<"<0>退出\n">; printf<"请输入您的选择:">; scanf<"%d",&sel>;printf<"%d",sel>; system<"cls">; switch<sel> { case1:T=ReadExpr<T>;break; case2:T=WriteExpr<T>;break; case3:T=Assign<T>;break; case4:T=Value<T>;break; case5:CompoundExpr<T>;break; case6:MergeConstruction<T>;break; case0:printf<"已退出!\n">;break; } }while<sel!=0>;}构建二叉树函数：BitTreeCreatBitTree<BitTreeT,BitTreep>{ charch; ch=getche<>; if<In<ch>==0> { printf<"\n表达式有误,请重新输入:\n">; T=CreatBitTree<T,p>; returnT; } T=<BitTree>malloc<sizeof<BitNode>>; if<T==NULL> {printf<"有错\n">;} else { if<In<ch>==2> { if<ch=='x'> { xflag=1; assg=0; T->data=ch; T->opnd=0; } else { T->data='N'; T->opnd=ch-'0'; } } elseif<In<ch>==1> { T->data=ch; T->opnd=0; } T->parent=p; p=T; if<In<ch>==2> { T->lchild=NULL; T->rchild=NULL; } elseif<In<ch>==3> { T->lchild=CreatBitTree<T->lchild,p>; T->rchild=NULL; } else { T->lchild=CreatBitTree<T->lchild,p>; T->rchild=CreatBitTree<T->rchild,p>; } } returnT;}中序遍历二叉树输出带括号中缀表达式的函数：voidInOrderTraverse<BitTreeT>{ if<T==NULL> return; else { if<Precede<T->data,T->parent->data>==-1> { printf<"<">; InOrderTraverse<T->lchild>; if<T->data=='N'> { printf<"%d",T->opnd>; } else { printf<"%c",T->data>; } InOrderTraverse<T->rchild>; printf<">">; } else { InOrderTraverse<T->lchild>; if<T->data=='N'> { printf<"%d",T->opnd>; } else { printf<"%c",T->data>; } InOrderTraverse<T->rchild>; }}}中序遍历二叉树给变量x赋值的函数：voidInOrder<BitTreeT,int*num>{ if<T==NULL> return; else { if<Precede<T->data,T->parent->data>==-1> { printf<"<">; InOrder<T->lchild,num>; if<T->data=='N'> { printf<"%d",T->opnd>; } elseif<T->data=='x'> {T->opnd=*num; printf<"%d",T->opnd>; } else printf<"%c",T->data>; InOrder<T->rchild,num>; printf<">">; } else {InOrder<T->lchild,num>; if<T->data=='N'> {printf<"%d",T->opnd>;} elseif<T->data=='x'> { T->opnd=*num; printf<"%d",T->opnd>; } else printf<"%c",T->data>; InOrder<T->rchild,num>; }}}后序遍历二叉树求表达式值的函数：voidPostOrderTraverse<BitTreeT>{if<T==NULL> return; else { PostOrderTraverse<T->lchild>; PostOrderTraverse<T->rchild>; if<In<T->data>==2> return; elseif<In<T->data>==1> T->opnd=calculate<T->lchild->opnd,T->data,T->rchild->opnd>;}}构造复合表达式的函数：voidCompoundExpr<BitTreeT>{ charoptr; BitTreeT1=NULL,T2=NULL; BitTreep; p=T1; printf<"请以字符序列的形式输入语法正确的前缀表示式E1:\n">; T1=CreatBitTree<T1,p>; T1->parent=T1; printf<"\n二叉树构造成功!\n">; p=T2; printf<"请以字符序列的形式输入语法正确的前缀表示式E2:\n">; T2=CreatBitTree<T2,p>; T2->parent=T2; printf<"\n二叉树构造成功!\n">; printf<"请输入运算符p:">; getchar<>; scanf<"%c",&optr>; T->data=optr; T->opnd=0; T->parent=T; T->lchild=T1; T->rchild=T2; T1->parent=T; T2->parent=T; flag=1;}化简函数表达式的函数：voidMergeConstruction<BitTreeT>{inta=1; printf<"化简后表达式为:">; while<a==1> {a=0; huajian<T,&a>; } InOrderTraverse<T>; printf<"\n">;}voidhuajian<BitTreeT,int*a>{ if<T==NULL> return; else {huajian<T->lchild,a>; if<In<T->data>==1&&T->lchild->data=='N'&&T->rchild->data=='N'> { T->opnd=calculate<T->lchild->opnd,T->data,T->rchild->opnd>; T->data='N'; T->lchild=NULL; T->rchild=NULL; *a=1; } huajian<T->rchild,a>; }}开始主要函数的程序流程图,实现设计中主程序和其他子模块的算法,以流程图的形式表示。开始输入选项输入选项yesCreatBitTree<BitTreeT,BitTreep>yesCreatBitTree<BitTreeT,BitTreep>ReadExpr<T>;选项1ReadExpr<T>;选项1nonoInOrderTraverse<BitTreeT>InOrderTraverse<BitTreeT>yesWriteExpr<BitTreeT>WriteExpr<BitTreeT>选项2nonoyesyesInOrder<BitTreeT,int*num>AssignInOrder<BitTreeT,int*num>Assign<BitTreeT>选项3nonoyesyesPostOrderTraverse<BitTreeT>Value<BitTreeT>PostOrderTraverse<BitTreeT>Value<BitTreeT>选项4nonoyesyesCreatBitTree<BitTreeT,BitTreep>CompoundExr<BitTreeT>选项5CreatBitTree<BitTreeT,BitTreep>CompoundExr<BitTreeT>选项5nonoyesyesHuajian<BitTreeT,int*a>MergeConstruction<BitTreeT>Huajian<BitTreeT,int*a>MergeConstruction<BitTreeT>选项6nonoyesyes选项0选项0nono结束结束画出函数之间的调用关系图。BitTreeReadExpr<BitTreeT>;BitTreeReadExpr<BitTreeT>;CreatBitTree<BitTreeT,BitTreep>CreatBitTree<BitTreeT,BitTreep>BitTreeWriteExpr<BitTreeT>BitTreeWriteExpr<BitTreeT>InOrderTraverseInOrderTraverse<BitTreeT>BitTreeAssign<BitTreeT>;BitTreeAssign<BitTreeT>;InOrder<BitTreeT,int*num>InOrder<BitTreeT,int*num>Voidmenu〔Intmain〔BitTreeValue<BitTreeT>;Voidmenu〔Intmain〔BitTreeValue<BitTreeT>;PostOrderTraverse<BitTreeT>PostOrderTraverse<BitTreeT>voidCompoundExpr<BitTreeT>;voidCompoundExpr<BitTreeT>;CreatBitTree<BitTreeT,BitTreep>CreatBitTree<BitTreeT,BitTreep>voidMergeConstruction<BitTreeT>;voidMergeConstruction<BitTreeT>;HuajianHuajian<BitTreeT,int*a>调试分析实际完成的情况说明〔完成的功能,支持的数据类型等；〔1以字符序列的形式输入正确的前缀表达式。〔2用带括号的中缀表达式输出表达式。〔3实现对变量x的赋值,初始值为0。〔4对算术表达式求值。〔5构造新的复合表达式。〔6>对表达式化简。2.程序的性能分析,包括时空分析；本程序实现了通过遍历二叉树对表达式的求值,化简等操作。此外,可以增加一些其他的操作或者增加一些其他的运算操作。3.上机过程中出现的问题及其解决方案；构建的二叉树为空。解决方案：通过传地址的方式调用二叉树操作函数。运行程序是无法输入字符。解决方案：用ch=getche<>;语句接收字符。使用数学函数时出错。解决方案：添加头文件#include<math.h>。程序中可以改进的地方说明；本程序运算数的输入输出局限于无符号整型数据,运算符的输入输出包括"+、-、*、/、^"。可以通过改进实现对浮点型数据的计算。另外,可以增加一些其他的运算,例如三角函数,指数函数等等。程序中可以扩充的功能及设计实现假想。程序可以增加对操作符sin,cos,tan,cot