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

《数据结构课程设计-利用栈求表达式的值》由会员分享，可在线阅读，更多相关《数据结构课程设计-利用栈求表达式的值（21页珍藏版）》请在装配图网上搜索。

1、课 程 设 计 报 告题目十三、利用栈求表达式的值一、 设计任务与目标编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式，以“=” 号结束表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。附加功能：1. 规定表达式的合法性2. 小数计算3. 计算记录的保存与查看4.（1）规定表达式的合法性，括号

2、配对，不能出现“6+3”、“6+3”等符号重叠的情况。（2）表达式开头只能是数字或“（”，表达式中只能有一个“=”。程序中应主要包含下面几个功能函数：void initstack()：初始化堆栈int make_str()：语法检查并计算int push_num(double num)：将操作数压入堆栈char procede(char top,char code)：处理操作码int change_opnd(int operate)：将字符型操作码转换成优先级int change_opnd(char code)：将操作码压入堆栈char pop_opnd(opnd *op)：将操作码弹出堆栈i

3、nt caculate(int cur_opnd)：简单计算+，-，*，/double pop_num(num *nu)：弹出操作数二、 方案设计与论证1. 定义一个expression全局表达式结构体expr1000存放计算过的表达式(expstrMAXSIZE)和计算结果(result)、一个计量器(i)、一个表达式字符串、 一个操作码栈和一个操作数栈；2. 把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；3. 第一个字符只能是数字或“（”，最重一个字符只能是“=”；4. 表达式括号必须配对，中间不能出现“=”；5. 在“（”前面只能是“+、*、/、( ”，在“+、*、/、=、

4、)”前面只能是数字或“）”；6. 把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；7. 把字符根据运算优先级别选择操作；8. 把表达式中的数值部分字符串转成数值压入操作数栈；9. 是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；10. 级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；11. 是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；12. 最后计算出结果并将其存放在expri，计量器加1；13. 重复计算后，将结果保存在文件里，并统计计算次数；14. 查

5、看多次计算结果，以表形式输出；15. 查看本次计算记录，以表形式输出；16. 清除计算记录，重新计算。三、 算法说明(一) 程序总共有如下函数：主要函数：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)/简单计算+，-，*，/表达式处理函数：in

6、t 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

7、(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

8、() 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()函数：调用了一个函数s

9、tart()，start()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str()并计算表达式result(op,nu)的操作。 result(op,nu)函数：是计算表达式，调用了初始化栈函数和字符级别判断change_opnd(*ps)，若是数字，则调用转化数字change_num(str2)然后压入操作数栈，若是运算符，刚调用判断操作procede(get_opnd(op),*ps)，若是“”，则弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算caculate(op,nu)后再压入操作数栈，计算完毕后按sta

10、rt()顺序运行。 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 expstrMA

11、XSIZE;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(T

12、he 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;elsere

13、turn 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-t

14、op=-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 -:

15、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 ()

16、;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)=s

17、tr)/没有输入小数点前的数，如“.032”p=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;else

18、if(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

19、(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(chang

20、e_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

21、(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)=)/检查是表达式和操作码是否到尾i

22、f(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(o

23、p)=)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+;f

24、or(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;frea

25、d(&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)”。

26、);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();els

27、eif(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);

28、/计算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;/操作

29、码栈num nu;/操作数栈printf(nt-计算表达式-nn);help();start(&op,&nu);/启动程序五、 程序运行的测试与分析A组：测试输入：1+2=、2-1=、3*3=、6/3=；测试目的：两个单位数的四则运算；正确输出：3、1、9、2；实际输出：3、1、9、2；当前状态：通过；B组：测试输入：12+12-12=、12*12/12=、12+12*12/12-(12/12-1+1*12-12)=；测试目的：多个两位数括号的混合四则运算；正确输出：12、12、24；实际输出：12、12、24；当前状态：通过；C组：测试输入：123+123-123*123+(123*(123

30、-(123/123*1+1)=；测试目的：多个三位数带多层括号的混合四则运算；正确输出：0；实际输出：0；当前状态：通过；D组：测试输入：12.3*12.3+(12.3+(12.3-(123*.1-12.3)*123*0.1-12.3)-12.3=(2+(4*5+3)*5)*2=,(2.5+(4.0*2+.1)*3=测试目的：多个小数带多层括号的混合四则运算，特别“.1”和“0.1”；正确输出：0、234、31.8；实际输出：0、-f0fad、-f0fad；当前状态：已更正，通过；E组：测试输入：12*(0-12)+(0-12)*12)+(0-12)*12-12*(0-12)*3= 1.2*(

31、0-1.2)+(0-1.2)*1.2)+(0-1.2)*1.2-1.2*(0-1.2)*3=测试目的：负数带括号的混合四则运算；正确输出：0、0；实际输出：0、0；当前状态：通过；六、结论与心得1、设计中遇到的问题及解决过程调试过程中出现一些逻辑和语法错误，但是语法错误容易纠正，而逻辑错误则比较难纠正，需要通过多次调试，找出过程中的漏洞。在设计数值转换时，只有抓住小数点为中界条件，找出整数位数和小数位数；在保存计算记录时，不能重复保存，需要断点。这些问题都是靠仔细分析，逐步琢磨出来的，要勤动手，先设计，后实现。2、设计体会和收获。 发现自己也能解决有点复杂的问题,程序设计思想上有了很大的提高，

32、学会了仔细分析问题的关键和辅助功能，在应用上设计程序要符合大众化的思维方式。3、因为时间问题，只能做出表达式基本运算，在以后的时间里，我会改善这个计算程序，让它能计算更复杂的表达式，如加上sin,cos时的运算。七、参考资料算法与数据结构C语言版 主编：陈守孔 机械工业出版社C程序设计 主编：谭浩强 清华大学出版社课程设计成绩评定表对课程设计工作过程的简短介绍和自我评价在课程设计工作过程中，我经过对利用栈求表达式程序的计算，保存，查看功能仔细分析后，逐步完善各种功能，在各个阶段中我积极探讨系统存在的问题，查阅资料解决问题，最终完成任务。经过这次课程设计，我的算法思想有很大的提高，对数据结构的熟练程度也加强了，学习掌握许多C语言上的知识，算法设计也更上一层楼。 学生签名：2010年 10 月31日（以下由评定小组教师填写）质量评价指标（在相应栏目打）评 价 项 目评 价 质 量优秀良好一般及格不及格工作量和态度实验、计算可靠性文字和图表质量总体评价评定成绩（百分制）评定小组成员签名2010年 月 日制定人：王钲璇，冯广慧 审定人： 陈守孔