数据结构课程设计之利用栈求表达式的值.docx

*大学数据结构课程设计报告题目：利用栈求表达式的值院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期: 2011、6、30指导教师: 指导教师评语： 成绩： 签名： 年 月 日20XX20XX年度 第 2 学期 一、需求分析1、从键盘上输入表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：void initstack()：初始化堆栈 int Make_str()：语法检查并计算 int push_operate(int operate)：将操作码压入堆栈 int push_num(double num)：将操作数压入堆栈 int procede(int operate)：处理操作码 int change_opnd(int operate)：将字符型操作码转换成优先级 int push_opnd(int operate)：将操作码压入堆栈 int pop_opnd()：将操作码弹出堆栈 int caculate(int cur_opnd)：简单计算+，-，*，/ double pop_num()：弹出操作数二、 概要设计1. 定义一个expression全局表达式结构体expr1000存放计算过的表达式(expstrMAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、 一个操作码栈和一个操作数栈；2. 把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；3. 第一个字符只能是数字或“（”，最重一个字符只能是“=”；4. 表达式括号必须配对，中间不能出现“=”；5. 在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、)”前面只能是数字或“）”；6. 把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；7. 把字符根据运算优先级别选择操作；8. 把表达式中的数值部分字符串转成数值压入操作数栈；9. 是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；10. 级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；11. 是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；12. 最后计算出结果并将其存放在expri，计量器加1；13. 重复计算后，将结果保存在文件里，并统计计算次数；14. 查看多次计算结果，以表形式输出；15. 查看本次计算记录，以表形式输出；清除计算记录，重新计算三、 详细设计 (一) 程序总共有如下函数：主要函数：void start(opnd *op,num *nu)/程序主菜单void start2(opnd *op,num *nu)/第二层计算选择，子菜单void load()/显示所有计算记录void save()/保存计算结果void check()/显示本次计算结果void result(opnd *op,num *nu)/计算结果double caculate(opnd *op,num *nu)/简单计算+，-，*，/表达式处理函数：int make_str()/语法检查double change_num(char str)/数字字符串转成double型数字char procede(char top,char code)/处理操作码，判断栈的操作int change_opnd(char code)/字符型操作码转换优先级，非表达式字符返回-2栈操作函数：double get_num(num *nu)/查看操作数栈栈顶double pop_num(num *nu)/操作数栈出栈int push_num(num *nu,double da)/压入操作数栈int empty_num(num *nu)/判空void initstack(num *nu)char get_opnd(opnd *op)/查看栈顶char pop_opnd(opnd *op)/出栈int push_opnd(opnd *op,char co)/压栈int empty_opnd(opnd *op)/判空void initstack(opnd *op)/初始化栈(二) 函数间的调用关系：l main()：主函数 start();load() start();l start()程序模式函数清空文件exit();make_str()result(op,nu) start2()start(); load start();l start2()子菜单 save() start2(); check() start2();l result(op,nu)计算结果initstack(op) initstack(nu) push_opnd(op,=) push_num(nu,change_num(str2);change_opnd(*ps) push_opnd(op,*ps)；procede(get_opnd(op),*ps) pop_opnd(op); push_num(nu,caculate(op,nu)l caculate(op,nu) b=pop_num(nu) a=pop_num(nu) pop_opnd(op) main()函数：调用了一个函数start()，start()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str()并计算表达式result(op,nu)的操作。 result(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*ps)，若是“”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按start()顺序运行。 start2()函数：在计算结果后调用跟随的选择菜单，进行查看结果check()、保存结果save()、查看计算记录load()、回到主菜单的操作。(三) 流程图:load()mainstart()result()save()ClearFileExit()Start2()check()（四）源代码：#include #include #include #include #define MAXSIZE 100#define N 1000int i=0;/表达式数struct expression/表达式结构long double result;char expstrMAXSIZE;exprN;/表达式的一个整体容器stypedef struct/操作码栈定义char codeMAXSIZE;int top;opnd;typedef struct/操作数栈定义double dateMAXSIZE;int top;num;/-opnd栈操作-：void initstack(opnd *op)/初始化栈op-top=-1;int empty_opnd(opnd *op)/判空if(op-top=-1)return 0;else return 1;int push_opnd(opnd *op,char co)/压栈if(op-top=MAXSIZE-1)printf(The opnd stack is full.);return 0;op-top+;op-codeop-top=co;return 1;char pop_opnd(opnd *op)/出栈char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;a=op-codeop-top;op-top-;return a;char get_opnd(opnd *op)/查看栈顶char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;elsereturn op-codeop-top;/-num栈操作-：void initstack(num *nu)nu-top=-1;int empty_num(num *nu)/判空if(nu-top=-1)return 0;else return 1;int push_num(num *nu,double da)/压栈if(nu-top=MAXSIZE-1)printf(error:The date stack is full.);return 0;nu-top+;nu-datenu-top=da;return 1;double pop_num(num *nu)/出栈double a=0;if(nu-top=-1)printf(error:The date stack is empty.);return a;a=nu-datenu-top;nu-top-;return a;double get_num(num *nu)/查看栈顶if(nu-top!=-1)return nu-datenu-top;/-结束栈定义操作-/-函数操作-：int change_opnd(char code)/将字符型操作码转换成优先级，非表达式字符反回-2switch(code)case =:return 1;break;case ):return 2;break;case +:return 3;break;case -:return 3;break;case *:return 4;break;case /:return 4;break;case (:return 0;break;/操作码级别=0;case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:case 0:case .: return -1;/操作数级别=-1；default: return -2;/其它符号级别=-2char procede(char top,char code)/处理操作码，判断栈的操作if(change_opnd(code)=0)/（入栈return ();elseif(change_opnd(code)=2&change_opnd(top)=0)/（和）同时出现，（出栈，）不入栈return (=);elseif(change_opnd(code);elsereturn ();/入栈double change_num(char str)/数字字符串转成double型数字char *s=str;int p=1,q=0;/p=小数点前位数，q=小数点后位数char d=.,z=0;double da=0;if(strstr(str,d)=0)/判断是否有小数点p=strlen(str);elseif(strstr(str,d)=str)/没有输入小数点前的数，如.032p=1;q=strlen(str)-1;strcpy(str,strcat(z,str);elsep=strstr(str,d)-str;q=strlen(str)-p-1;for(int i=0;ip;i+)/小数点前的各位数乘以各自的阶数，然后叠加：123=1*100+2*10+3*1da=da+(int)stri-48)*pow(10,p-i-1);for(int j=0;j0)printf(n表达式只能以数字或(开头。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;elseif(change_opnd(*p)=-2)printf(n表达式%c为非法字符。请重新输入：,*p);gets(expri.expstr);p=expri.expstr;n=0;continue;else/合法刚跳到下一个字符p=p+1;continue;if(change_opnd(*p)=-2)/非法字符判断printf(n表达式%c为非法字符。请重新输入：,*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)=0)/(前一个字符只能是+、-、*、/、(if(change_opnd(*(p-1)4)if(change_opnd(*(p-1)!=0)printf(n表达式%c或%c不符合语法。请重新输入：,*(p-1),*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)0)/+、-、*、/、=、)前一个字符只能是数字和)if(change_opnd(*(p-1)!=-1)if(change_opnd(*(p-1)!=2)printf(n表达式%c或%c不符合语法。请重新输入：,*(p-1),*p);gets(expri.expstr);p=expri.expstr;n=0;continue;if(change_opnd(*p)=1)/判断表达式中是否有=重复出现，最后括号是否配对if(*(p+1)!=0)printf(n表达式中=，只能出现在表达式结束处。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;if(n!=0)printf(n表达式括号不配。请重新输入：);gets(expri.expstr);p=expri.expstr;n=0;continue;p=p+1;return 1;double caculate(opnd *op,num *nu)/简单计算+，-，*，/double b=pop_num(nu),a=pop_num(nu);switch(pop_opnd(op)case +:return(a+b);break;case -:return(a-b);break;case *:return(a*b);break;case /:return(a/b);break;void result(opnd *op,num *nu)/计算结果char str2MAXSIZE=,str32=0;char *ps=expri.expstr;initstack(op);/初始化栈initstack(nu);push_opnd(op,=);while(!(*ps=)&(get_opnd(op)=)/检查是表达式和操作码是否到尾if(change_opnd(*ps)=-1)/操作数处理while(change_opnd(*ps)=-1)strncpy(str3,ps,1);/数字字符一个个取出放在str2strcat(str2,str3);ps+;push_num(nu,change_num(str2);strcpy(str2,);else /操作码处理switch(procede(get_opnd(op),*ps)case :push_num(nu,caculate(op,nu);continue;break;if(*ps=)&get_opnd(op)=)ps+;continue;if(*ps=|get_opnd(op)=)continue;/表达式和操作码有一个到尾，则跳出继续循环ps+;expri.result=get_num(nu);printf(nt 表达式：%st计算结果：%lfn,expri.expstr,expri.result);printf(t-n);i+;/表达式个数加1；void check()/显示计算结果for(int n=0;n0;n-)/记录最后一个#号位置，即未保存的结果的开始位置,重复保存只会追加if(exprn-1.expstr0=#)break;strcpy(expri.expstr,#表达式个数：);/每次保存都统计计算次数expri.result=i-n;i+;for(m=n;mi;m+)if(fwrite(&exprm,sizeof(struct expression),1,fp)!=1)/将表达式和计算结果存到文件中printf(file write errorn);fclose(fp);printf(*提醒：计算记录已经保存n);void load()/显示所有计算记录int m;expression eN;FILE *fp;printf(n);if(fp=fopen(calculate.dat,rb)=NULL)/空文件printf(t-n);printf(*提醒：没有记录信息，请进行计算并保存信息:n);return;for(m=0;fread(&em,sizeof(struct expression),1,fp);m+)/按照expression结构一个个读取printf(t%d -n,m+1);printf(t 表达式：%st计算结果：%.2lfn,em.expstr,em.result);if(em.expstr0=#)/控制输出不同次计算的记录m=-1;printf(n);printf(t-n);fclose(fp);printf(n);void help()printf(t 表达式计算，请用户正确输入表达式，不得出现非法字符及字符nt重复出现，表达式以=号结尾，若计算到负数，如-20，请输nt入(0-20)。);printf(请用户及时保存计算结果以便查看，每次回到主菜单nt时，若没有保存结果，则当次计算结果会被清除。n);void start(opnd *op,num *nu);void start2(opnd *op,num *nu)/第二层计算选择菜单char r;while(1)printf(t-n);printf(nttt查看本次计算记录，请输入r或Rnnttt保存本次计算记录，请输入s或Snnttt查看所有计算记录，请输入l或Lnnttt回到主菜单，按任意键返回ntt:);scanf(%s,&r);if(r=r|r=R)check();elseif(r=s|r=S)save();elseif(r=l|r=L)load();elsei=0;start(op,nu); void start(opnd *op,num *nu)/程序主导char ch,c,g;g=Y;printf(nttt查看记录，请输入l或Lnnttt清空记录，请输入C或cnnttt计算式子，请输入Y或ynnttt退出程序，按任意键退出ntt:);scanf(%s,&c);getchar(ch);if(c=l|c=L)load();start(op,nu);elseif(c=Y|c=y)while(1)if(g=Y|g=y)if(make_str()/语法检查printf(t-n);result(op,nu);/计算elseprintf(nt*提醒：计算结束！nn);break;printf(n继续计算，请输入Y或y，否则按任意键结束计算:);scanf(%s,&g);getchar(ch);start2(op,nu);else if(c=C|c=c)/清空文件/*FILE *fp;fp=fopen(calculate.dat,w);fclose(fp);*/printf(t-n);remove(calculate.dat);printf(*提醒：所有记录已经清空。);start(op,nu);elseprintf(nt*提醒：结束！n);exit(0);void main()opnd op;/操作码栈num nu;/操作数栈printf(nt-计算表达式-nn);help();start(&op,&nu);/启动程序四、 调试分析 测试输入：13*5+6/2-4=测试目的：简单加减乘除正确输出：64；实际输出：64测试输入：123+123-123*123+(123*(123-(123/123*1+1)=；测试目的：多个三位数带多层括号的混合四则运算；正确输出：0；实际输出：0；五、 测试结果六、 用户手册定义一个expression全局表达式结构体expr1000存放计算过的表达式(expstrMAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、 一 个操作码栈和一个操作数栈；把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；第一个字符只能是数字或“（”，最重一个字符只能是“=”；表达式括号必须配对，中间不能出现“=”；在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、)”前面只能是数字或“）”；把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；把字符根据运算优先级别选择操作；把表达式中的数值部分字符串转成数值压入操作数栈；七、 体会与自我评价 在为期不到两周的课程设计中，我体会颇多，学到很多东西。自己通过复习了自己以前的知识，自己的逻辑思考能力也提高不少。从而对Microsoft Visual C+ 6.0又有了更深入的认识！在这次课程设计中，我还懂得了程序开发的一些比较重要的步骤，比如需求分析、总体设计、数据库设计(含概念设计、逻辑设计、物理设计)、程序模块设计(含功能需求、用户界面设计、程序代码设计与分析、运行结果)、系统使用说明等。总之，通过这次课程设计，我收获颇丰，相信会为自己以后的学习和工作带来很大的好处。最重要的还是激发了我编程的兴趣和热情，让我从一个只懂理论变成了能做一些小型程序，让我对编程更加热爱了。整体地评价这次课程设计，我认为收获很大，正如上面所说的那样，通过课程设计，既复习了以前的旧知识，又学到了一些新的知识；设计增强了我们用所学知识去解决具体问题的能力，进一步培养了我们独立思考问题和解决问题的能力。特别是学会了在Visual C+ 集成开发环境中如何调试程序的方法。当然，老师的悉心指导和同学的帮助也是不可忽视的，在此感谢本次课程设计中所有辅导老师对我的关心和帮助，诚心诚意感谢他们对我的鼓励与教导，是她们在我迷茫的时候给了我些许提示，激发了我编程的灵感；还有，我在此也十分感谢本次课程设计中同学们对我的帮助，尽管本次不是团队合作，但是他们也给了我不少的提示和帮助，是他们让我有信心坚持做下来，在此感谢他们！调试过程中出现一些逻辑和语法错误，但是语法错误容易纠正，而逻辑错误则比较难纠正，需要通过多次调试，找出过程中的漏洞。在设计数值转换时，只有抓住小数点为中界条件，找出整数位数和小数位数；在保存计算记录时，不能重复保存，需要断点。这些问题都是靠仔细分析，逐步琢磨出来的，要勤动手，先设计，后实现。发现自己也能解决有点复杂的问题,程序设计思想上有了很大的提高，学会了仔细分析问题的关键和辅助功能，在应用上设计程序要符合大众化的思维方式。源代码#include #include #include #include #define MAXSIZE 100#define N 1000int i=0;/表达式数struct expression/表达式结构long double result;char expstrMAXSIZE;exprN;/表达式的一个整体容器stypedef struct/操作码栈定义char codeMAXSIZE;int top;opnd;typedef struct/操作数栈定义double dateMAXSIZE;int top;num;/-opnd栈操作-：void initstack(opnd *op)/初始化栈op-top=-1;int empty_opnd(opnd *op)/判空if(op-top=-1)return 0;else return 1;int push_opnd(opnd *op,char co)/压栈if(op-top=MAXSIZE-1)printf(The opnd stack is full.);return 0;op-top+;op-codeop-top=co;return 1;char pop_opnd(opnd *op)/出栈char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;a=op-codeop-top;op-top-;return a;char get_opnd(opnd *op)/查看栈顶char a=0;if(op-top=-1)printf(error:The opnd stack is empty.);return a;elsereturn op-codeop-top;/-num栈操作-：void initstack(num *nu)nu-top=-1;int empty_num(num *nu)/判空if(nu-top=-1)return 0;else return 1;int push_num(num *nu,double da)/压栈if(nu-top=MAXSIZE-1)printf(error:The date stack is full.);return 0;nu-top+;nu-datenu-top=da;return 1;double pop_num(num *nu)/出栈double a=0;if(nu-top=-1)printf(error:The date stack is empty.);return a;a=nu-datenu-top;nu-top-;return a;double get_num(num *nu)/查看栈顶if(nu-top!=-1)return nu-datenu-top;/-结束栈定义操作-/-函数操作-：int change_opnd(char code)/将字符型操作码转换成优先级，非表达式字符反回-2switch(code)case =:return 1;break;case ):return 2;break;case +:return 3;break;case -:return 3;break;case *:return 4;break;case /:return 4;break;case (:return 0;break;/操作码级别=0;case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:case 0:case .: return -1;/操作数级别=-1；default: return -2;/其它符号级别=-2char procede(char top,char code)/处理操作码，判断栈的操作if(change_opnd(code)=0)/（入栈return ();elseif(change_opnd(code)=2&change_opnd(top)=0)/（和）同时出现，（出栈，）不入栈return