表达式求值 二叉树 zstu 08 袁景华.docx

1、表达式求值 二叉树 zstu 08 袁景华表达式求值 二叉树 zstu 08 袁景华表达式求值-二叉树-zstu-08-袁景华2010-12-14 22：56一、程序设计的基本思想，原理和算法描述：表达式建树原理：对表达式先找到运算级最低的运算操作符，并将其作为该表达式的根结点，该运算符左右两段表达式分别作为其左右子树。1.若该运算操作符位于表达式首，则其一定是-，此时左子树为空；2.若该运算操作符是一对括弧(括弧嵌套情况)则化简(把括弧去掉)，对表达式构造二叉树；表达式不合法情况：1.表达式首为：+、*、/、.、)；2.表达式尾为：+、-、*、/、.、(；表达式合法情况：1.表达式非首位置：

2、a.(之前只能为：+、-、*、/、(；b.)之前只能为：)、数字0-9；c.+、*、/之前只能为：)、数字0-9；d.-之前只能为：(、)、数字0-9；e.之前只能为：数字0-9；表达式求值：将操作数全部转化为double数据类型进行求解。测试数据：1.-(2.5+2.5)/(3-1)*4+(10-8)*6)/(4-2)+(-2*(4+1)/(3-1)*2+1)+1 2.-(3-1)/2+2.5-(3-4+6)/2-3*2/1)+1.5)*2-3*3/2/(5-3)3.1000000000*2000000000/4 4.200.3.3*32.1 5.99999/11 6.(45-33)*2-3

3、+4/2*5-3 7.-(45-33)*2-3+4/2*5-3二、源程序及注释：/ExpnBiTree.cpp#include stdio.h#include string.h#include stdlib.h#define STATUS int#define OK 1#define ERROR 0#define EXP_LEN 100/定义表达式的最大长度#define DATA_LEN 20/定义每个操作数的最大长度typedef struct BinaryTreeint dflag；/标志域，值为1，data存放操作运算符；值为0，data存放操作数char dataDATA_LEN+1

4、；/数据域，存放：操作运算符或操作数struct BinaryTree*lchild,*rchild；/分别指向结点的左、右子树BiTNode,*BiTree；/定义二叉树结点及二叉树类型指针STATUS CreateBiTree(BiTree&bt,char*p,int l)；/创建二叉树，并用bt返回树的根地址，p为表达式的首地址，l为表达式的长度STATUS Calculate(BiTree bt,double&rst)；/计算表达式的值，bt为据表达式创建的二叉树，用rst返回表达式的值STATUS PreOrderTraverse(BiTree bt)；/先序遍历二叉树bt，输出先序

5、遍历序列STATUS InOrderTraverse(BiTree bt)；/中序遍历二叉树bt，输出中序遍历序列STATUS PostOrderTraverse(BiTree bt)；/后序遍历二叉树bt，输出后序遍历序列STATUS DestroyBiTree(BiTree&bt)；/销毁二叉树void main()int n,l,i；/n标志量，值为0，退出程序；l存储表达式的长度；i一般变量char expnEXP_LEN+1；/存放表达式double rst；/存放表达式计算结果BiTree bt=NULL；/声明一个二叉树doi=0；printf(请输入合法的表达式：n)；gets

6、(expn)；for(i=0,l=0；expni！=message；i+)/去掉表达式中的空格，并计算表达式的长度if(expni！=)expnl+=expni；expnl=message；printf(正在构建二叉树n)；if(CreateBiTree(bt,expn,l)printf(二叉树构建成功！n)；else/销毁未成功建立的二叉树，释放动态申请的内存printf(二叉树构建失败！n)；printf(将销毁二叉树)；if(DestroyBiTree(bt)printf(二叉树销毁成功！n)；elseprintf(二叉树销毁失败！n)；exit(0)；continue；printf(即

7、将输出表达式的先序遍历序列：n)；PreOrderTraverse(bt)；printf(n)；printf(即将输出表达式的中序遍历序列：n)；InOrderTraverse(bt)；printf(n)；printf(即将输出表达式的后序遍历序列：n)；PostOrderTraverse(bt)；printf(n)；printf(正在计算表达式的值：n)；if(Calculate(bt,rst)printf(%gn,rst)；else printf(计算表达式的值失败！n)；printf(即将销毁二叉树)；if(DestroyBiTree(bt)printf(二叉树销毁成功！n)；elsep

8、rintf(二叉树销毁失败！n)；exit(0)；printf(如果要继续计算下一个表达式，请输入一个非零整数，否则，请输入0：)；scanf(%d,&n)；getchar()；while(n)；STATUS CreateBiTree(BiTree&bt,char*p,int l)int i=0,lnum=0,rpst1=-1,rpst2=-1,pn=0；/lnum记录(的未成对个数；/rpst1/rpst2记录表达式中优先级最低的(*、/)/(+、-)的位置；/pn记录操作数中.的个数,以判断输入操作数是否合法if(l=0)return OK；if(！(bt=(BiTree)malloc(s

9、izeof(BiTNode)printf(内存申请失败n)；return ERROR；elsebt-lchild=bt-rchild=NULL；memset(bt-data,message,sizeof(bt-data)；bt-dflag=1；/默认bt为叶子节点(即，存放操作数)if(*p=+|*p=*|*p=/|*p=.|*p=)/表达式首不合法；printf(表达式输入错误！n)；return ERROR；if(！(*(p+l-1)=)|*(p+l-1)=0&*(p+l-1)=9)/表达式尾不合法；printf(表达式输入错误！n)；return ERROR；if(l=1)/此时只有表达

10、式为数字，表达式才合法if(*p0|*p9)printf(表达式输入错误！n)；return ERROR；elsebt-data0=*p；return OK；else if(l=2)/此时只有表达式为正数或负数，表达式才合法if(*p=-|*p=0&*p=9)&*(p+1)=0&*(p+1)=9)bt-data0=*p；bt-data1=*(p+1)；return OK；elseprintf(表达式输入错误！n)；return ERROR；elseif(*p=()lnum+；for(i=1；i l；i+)if(*(p+i)=.)if(！(*(p+i-1)=0&*(p+i-1)=9)printf

11、(表达式输入错误！n)；return ERROR；else if(*(p+i)=*|*(p+i)=/)if(！(*(p+i-1)=0&*(p+i-1)=9|*(p+i-1)=)printf(表达式输入错误！n)；return ERROR；if(lnum=0)rpst1=i；else if(*(p+i)=()if(*(p+i-1)=+|*(p+i-1)=-|*(p+i-1)=*|*(p+i-1)=/|*(p+i-1)=()lnum+；elseprintf(表达式输入错误！n)；return ERROR；else if(*(p+i)=)if(*(p+i-1)=)|*(p+i-1)=0&*(p+i-

12、1)=9)lnum-；elseprintf(表达式输入错误！n)；return ERROR；if(lnum 0)printf(表达式输入错误！n)；return ERROR；else if(*(p+i)=+|*(p+i)=-)if(*(p+i)=+&！(*(p+i-1)=0&*(p+i-1)=9|*(p+i-1)=)printf(表达式输入错误！n)；return ERROR；else if(*(p+i)=-&！(*(p+i-1)=0&*(p+i-1)=9|*(p+i-1)=)|*(p+i-1)=()printf(表达式输入错误！n)；return ERROR；if(lnum=0)rpst2=

13、i；if(lnum！=0)printf(表达式输入错误！n)；return ERROR；/(、)未能完全配对,表达式输入不合法if(rpst2-1)bt-dflag=0；bt-data0=*(p+rpst2)；if(CreateBiTree(bt-lchild,p,rpst2)if(CreateBiTree(bt-rchild,p+rpst2+1,l-rpst2-1)return OK；return ERROR；if(rpst1 0)/此时表明表达式或者是一个数字，或是表达式整体被一对括弧括起来if(*p=()/此时表达式整体被一对括弧括起来if(CreateBiTree(bt,p+1,l-2

14、)return OK；else return ERROR；elseif(*(p+1)！=()/此时表达式一定是一个数字for(i=0；i l；i+)if(*(p+i)=.)pn+；if(pn 1)printf(表达式输入错误！n)；return ERROR；bt-datai=*(p+i)；return OK；else/此时表达式首一定是操作符-，其余部分被一对括弧括起来bt-dflag=0；bt-data0=-；if(CreateBiTree(bt-rchild,p+2,l-3)return OK；else return ERROR；else/此时表明表达式为几个因子想成或相除而组成的bt-d

15、flag=0；bt-data0=*(p+rpst1)；if(CreateBiTree(bt-lchild,p,rpst1)if(CreateBiTree(bt-rchild,p+rpst1+1,l-rpst1-1)return OK；return ERROR；STATUS Calculate(BiTree bt,double&rst)double l=0,r=0；/l、r分别存放左右子树所代表的字表达式的值if(！bt)rst=0；return OK；if(bt-dflag=1)rst=atof(bt-data)；return OK；elseif(Calculate(bt-lchild,l)i

16、f(Calculate(bt-rchild,r)switch(bt-data0)case+：rst=l+r；break；case-：rst=l-r；break；case*：rst=l*r；break；case/：if(r=0)printf(除数为0！n)；return ERROR；elserst=l/r；break；default：return ERROR；/printf(%g%c%g=%gn,l,bt-data0,r,rst)；/输出运算过程return OK；return ERROR；STATUS PreOrderTraverse(BiTree bt)if(bt)printf(%s,bt-

17、data)；if(PreOrderTraverse(bt-lchild)if(PreOrderTraverse(bt-rchild)return OK；return ERROR；return OK；STATUS InOrderTraverse(BiTree bt)if(bt)if(InOrderTraverse(bt-lchild)printf(%s,bt-data)；if(InOrderTraverse(bt-rchild)return OK；return ERROR；return ERROR；return OK；STATUS PostOrderTraverse(BiTree bt)if(b

18、t)if(PostOrderTraverse(bt-lchild)if(PostOrderTraverse(bt-rchild)printf(%s,bt-data)；return OK；else return ERROR；return OK；STATUS DestroyBiTree(BiTree&bt)if(bt)if(DestroyBiTree(bt-lchild)if(DestroyBiTree(bt-rchild)free(bt)；return OK；else return ERROR；return OK；三、心得与体会：在考虑建树的如何建树过程中，思考了很长时间，通过和同学交流，把表达式可能出现的各种情况都注意到，使得建树函数对各种表达式都适用(括弧嵌套，并列)。考虑到实际情况，需要考虑各种不合法的表达式输入，并作出相应处理。大家在学习中需要交流；对待每一个问题，要多思考，保证程序严密无错！希望对大家有帮助，考虑非法表达式输入处理情况较复杂，难免有疏漏之处，如果有什么不妥之处，还请大家指出，谢谢！经过验证原先的代码有漏洞，故作了更改！现在应该没什么问题了