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

精选优质文档-----倾情为你奉上精选优质文档-----倾情为你奉上专心---专注---专业专心---专注---专业精选优质文档-----倾情为你奉上专心---专注---专业装订线实验报告装订线课程名称：程序设计与数据结构指导老师：ljq成绩：实验名称：基于二叉树结构的表达式求值算法实验类型：上机同组学生姓名：一、实验目的和要求（必填） 三、代码缺陷及修正记录五、讨论、心得二、实验内容和代码（必填）四、实验结果与分析（必填）一、实验目的和要求掌握编程工具的使用掌握二叉树数据结构在计算机上的实现掌握通过计算机编程解决问题的基本方法二、实验内容和代码实验内容：编程实现基于二叉树结构的表达式求值算法表达式包含加减乘除四则运算以及至少一层括弧运算首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历方法求得表达式的值将所有实验内容合并到一个工程，增加交互操作和循环处理（持续）代码1.头文件expnbitree.h1234567891011121314151617181920212223#include<stdio.h>#include<string.h>#include<stdlib.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);//销毁二叉树//二叉树结构的表达式求解算法入口voidexpnbitree();2.源文件expntree.c123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354#include<stdio.h>#include<string.h>#include<stdlib.h>#include"expnbitree.h"//ExpnBiTree实现子程序入口voidexpnbitree(){ intn,len,i;//n标志量,值为0,退出程序;len存储表达式的长度;i一般变量 charexpn[EXP_LEN+1];//存放表达式 doublerst;//存放表达式计算结果 BiTreebt=NULL;//声明一个二叉树 gets_s(expn); do { 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; } 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); else printf("计算表达式的值失败!\n"); printf("即将销毁二叉树…………"); if(DestroyBiTree(bt)) printf("二叉树销毁成功!\n"); else{ printf("二叉树销毁失败!\n"); exit(0); } printf("如果要继续计算下一个表达式,请输入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 { //初始化 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; } if(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; } //表达式合法，开始创建二叉树 else { if(*p=='(') lnum++; for(i=1;i<len;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; } 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(lnum<0){ printf("表达式输入错误!\n"); return0; } } 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"); return0; } //"("、")"未能完全配对,表达式输入不合法 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(rpst1<0)//此时表明表达式或者是一个数字,或是表达式整体被一对括弧括起来 { if(*p=='(')//此时表达式整体被一对括弧括起来 if(CreateBiTree(bt,p+1,len-2)) return1; elsereturn0; else { if(*(p+1)!='(')//此时表达式一定是一个数字 { for(i=0;i<len;i++) { if(*(p+i)=='.')pn++; if(pn>1){ printf("表达式输入错误!\n"); return0; } bt->data[i]=*(p+i); } return1; } else//此时表达式首一定是操作符"-",其余部分被一对括弧括起来 { bt->dflag=0;bt->data[0]='-'; if(CreateBiTree(bt->rchild,p+2,len-3)) return1; elsereturn0; } } } else//此时表明表达式为几个因子想成或相除而组成的 { bt->dflag=0;bt->data[0]=*(p+rpst1); if(CreateBiTree(bt->lchild,p,rpst1)) if(CreateBiTree(bt->rchild,p+rpst1+1,len-rpst1-1)) return1; return0; } } }}//计算表达式intCalculate(BiTreebt,double&rst){ doublel=0,r=0;//l、r分别存放左右子树所代表的字表达式的值 if(!bt){ rst=0; return1; } if(bt->dflag==1){ rst=atof(bt->data);//atof()，是C语言标准库中的一个字符串处理函数，//功能是把字符串转换成浮点数， //所使用的头文件为<stdlib.h>。该函数名是“asciitofloatingpointnumbers”的缩写。 //语法格式为：doubleatof(constchar*nptr)。 return1; } else { if(Calculate(bt->lchild,l))//后序 if(Calculate(bt->rchild,r)) { switch(bt->data[0]) { case'+':rst=l+r;break; case'-':rst=l-r;break; case'*':rst=l*r;break; case'/':if(r==0){ printf("除数为0!\n"); return0; } else{ rst=l/r; break; } default:return0; } //printf("%g%c%g=%g\n",l,bt->data[0],r,rst);//输出运算过程 return1; } return0; }}//先序遍历二叉树intPreOrderTraverse(BiTreebt){ if(bt) { printf("%s",bt->data); if(PreOrderTraverse(bt->lchild)) if(PreOrderTraverse(bt->rchild)) return1; return0; } return1;}//中序遍历二叉树intInOrderTraverse(BiTreebt){ if(bt) { if(InOrderTraverse(bt->lchild)) { printf("%s",bt->data); if(InOrderTraverse(bt->rchild)) return1; return0; } return0; } return1;}//后序遍历二叉树intPostOrderTraverse(BiTreebt){ if(bt) { if(PostOrderTraverse(bt->lchild)) if(PostOrderTraverse(bt->rchild)) { printf("%s",bt->data); return1; } elsereturn0; } return1;}//销毁二叉树intDestroyBiTree(BiTree&bt){ if(bt) { if(DestroyBiTree(bt->lchild)) if(DestroyBiTree(bt->rchild)) { free(bt);