基于二叉树结构的表达式求值算法

实验报告课程名称：程序设计与数据结构指导老师：ljq成绩：实验名称：基于二叉树结构的表达式求值算法实验类型：上机同组学生姓名：一、实验目的和要求（必填）三、代码缺陷及修正记录五、讨论、心得二、实验内容和代码（必填）四、实验结果与分析（必填）一、实验目的和要求1.掌握编程工具的使用2.掌握二叉树数据结构在计算机上的实现3.掌握通过计算机编程解决问题的基本方法二、实验内容和代码1．实验内容：编程实现基于二叉树结构的表达式求值算法表达式包含加减乘除四则运算以及至少一层括弧运算首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历方法求得表达式的值将所有实验内容合并到一个工程，增加交互操作和循环处理（持续）2．代码1.头文件expnbitree.h装订线12345678910111213141516171819202122#includestdio.h#includestring.h#includestdlib.h#defineEXP_LEN100//定义表达式的最大长度#defineDATA_LEN20//定义每个操作数的最大长度typedefstructBiTNode{intdflag;//标志域,值为1,data[]存放操作运算符;值为0,data[]存放操作数chardata[DATA_LEN+1];//数据域,存放:操作运算符或操作数structBiTNode*lchild,*rchild;//分别指向结点的左、右子树}BiTNode,*BiTree;//定义二叉树结点及二叉树类型指针intCreateBiTree(BiTree&bt,char*p,intlen);//创建二叉树,并用bt返回树的根地址,p为表达式的首地址,l为表达式的长度intCalculate(BiTreebt,double&rst);//计算表达式的值,bt为据表达式创建的二叉树,用rst返回表达式的值intPreOrderTraverse(BiTreebt);//先序遍历二叉树bt,输出先序遍历序列intInOrderTraverse(BiTreebt);//中序遍历二叉树bt,输出中序遍历序列intPostOrderTraverse(BiTreebt);//后序遍历二叉树bt,输出后序遍历序列intDestroyBiTree(BiTree&bt);//销毁二叉树//二叉树结构的表达式求解算法入口23voidexpnbitree();2.源文件expntree.c123456789101112131415#includestdio.h#includestring.h#includestdlib.h#includeexpnbitree.h//ExpnBiTree实现子程序入口voidexpnbitree(){intn,len,i;//n标志量,值为0,退出程序;len存储表达式的长度;i一般变量charexpn[EXP_LEN+1];//存放表达式doublerst;//存放表达式计算结果BiTreebt=NULL;//声明一个二叉树gets_s(expn);do16171819202122232425262728293031323334353637{i=0;printf(请输入合法的表达式:\n);gets_s(expn);for(i=0,len=0;expn[i]!='\0';i++)//去掉表达式中的空格,并计算表达式的长度if(expn[i]!='')expn[len++]=expn[i];expn[len]='\0';printf(正在构建二叉树……\n);if(CreateBiTree(bt,expn,len))printf(二叉树构建成功!\n);else{//销毁未成功建立的二叉树,释放动态申请的内存printf(二叉树构建失败!\n);printf(将销毁二叉树…………);if(DestroyBiTree(bt))printf(二叉树销毁成功!\n);else{printf(二叉树销毁失败!\n);exit(0);}continue;38394041424344454647484950515253545556575859}printf(输出表达式的先序遍历序列……:\n);PreOrderTraverse(bt);printf(\n);printf(输出表达式的中序遍历序列……:\n);InOrderTraverse(bt);printf(\n);printf(输出表达式的后序遍历序列……:\n);PostOrderTraverse(bt);printf(\n);printf(计算表达式的值……:\n);if(Calculate(bt,rst))printf(%g\n,rst);elseprintf(计算表达式的值失败!\n);printf(即将销毁二叉树…………);if(DestroyBiTree(bt))printf(二叉树销毁成功!\n);else{printf(二叉树销毁失败!\n);exit(0);}60616263646566676869707172737475767778798081printf(如果要继续计算下一个表达式,请输入1,否则,返回上一级:\n);scanf_s(%d,&n);getchar();}while(n==1);}//创建二叉树intCreateBiTree(BiTree&bt,char*p,intlen){inti=0,lnum=0,rpst1=-1,rpst2=-1,pn=0;//lnum记录(的未成对个数;//rpst1/rpst2记录表达式中优先级最低的(*、/)/(+、-)的位置;//pn记录操作数中.的个数,以判断输入操作数是否合法if(len==0)return1;if(!(bt=(BiTree)malloc(sizeof(BiTNode)))){printf(内存申请失败\n);return0;}else{828384858687888990919293949596979899100101102103//初始化bt-lchild=bt-rchild=NULL;memset(bt-data,'\0',sizeof(bt-data));//memset是计算机中C/C++语言函数——memset(void*s,intch,size_tn);//将s所指向的某一块内存中的后n个字节的内容全部设置为ch指定的ASCII值，//第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为s。bt-dflag=1;//默认bt为叶子节点(即,存放操作数)//合法性检查if(*p=='+'||*p=='*'||*p=='/'||*p=='.'||*p==')')//表达式首不合法;{printf(表达式输入错误!\n);return0;}if(!(*(p+len-1)==')'||*(p+len-1)='0'&&*(p+len-1)='9'))//不为右括弧或数字，则表达式尾不合法;{printf(表达式输入错误！\n);return0;}104105106107108109110111112113114115116117118119120121122123124125if(len==1)//此时只有表达式为数字,表达式才合法if(*p'0'||*p'9'){printf(表达式输入错误!\n);return0;}else{bt-data[0]=*p;return1;}elseif(len==2)//此时只有表达式为正数或负数,表达式才合法if((*p=='-'||*p='0'&&*p='9')&&*(p+1)='0'&&*(p+1)='9'){bt-data[0]=*p;bt-data[1]=*(p+1);return1;}else{printf(表达式输入错误!\n);return0;}//表达式合法，开始创建二叉树else126127128129130131132133134135136137138139140141142143144145146147{if(*p=='(')lnum++;for(i=1;ilen;i++){//合法性检查if(*(p+i)=='.'){if(!(*(p+i-1)='0'&&*(p+i-1)='9')){printf(表达式输入错误!\n);return0;}}elseif(*(p+i)=='*'||*(p+i)=='/'){if(!(*(p+i-1)='0'&&*(p+i-1)='9'||*(p+i-1)==')')){printf(表达式输入错误!\n);return0;}if(lnum==0)rpst1=i;148149150151152153154155156157158159160161162163164165166167168169}elseif(*(p+i)=='('){if(*(p+i-1)=='+'||*(p+i-1)=='-'||*(p+i-1)=='*'||*(p+i-1)=='/'||*(p+i-1)=='(')lnum++;else{printf(表达式输入错误!\n);return0;}}elseif(*(p+i)==')'){if(*(p+i-1)==')'||*(p+i-1)='0'&&*(p+i-1)='9')lnum--;else{printf(表达式输入错误!\n);return0;}if(lnum0){printf(表达式输入错误!\n);return0;170171172173174175176177178179180181182183184185186187188189190191}}elseif(*(p+i)=='+'||*(p+i)=='-'){if(*(p+i)=='+'&&!(*(p+i-1)='0'&&*(p+i-1)='9'||*(p+i-1)==')')){printf(表达式输入错误!\n);return0;}elseif(*(p+i)=='-'&&!(*(p+i-1)='0'&&*(p+i-1)='9'||*(p+i-1)==')'||*(p+i-1)=='(')){printf(表达式输入错误!\n);return0;}if(lnum==0)rpst2=i;}}if(lnum!=0){printf(表达式输入错误!\n);192193194195196197198199200201202203204205206207208209210211212213return0;}//(、)未能完全配对,表达式输入不合法if(rpst2-1)//+-{bt-dflag=0;//data[]存放操作数bt-data[0]=*(p+rpst2);if(CreateBiTree(bt-lchild,p,rpst2))if(CreateBiTree(bt-rchild,p+rpst2+1,len-rpst2-1))return1;return0;}if(rpst10)//此时表明表达式或者是一个数字,或是表达式整体被一对括弧括起来{if(*p=='(')//此时表达式整体被一对括弧括起来if(CreateBiTree(bt,p+1,len-2))return1;elsereturn0;214215216217218219220221222223224225226227228229230231232233234235else{if(*(p+1)!='(')//此时表达式一定是一个数字{for(i=0;ilen;i++){if(*(p+i)=='.')pn++;if(pn1){printf(表达式输入错误!\n);return0;}bt-data[i]=*(p+i);}return1;}else//此时表达式首一定是操作符-,其余部分被一对括弧括