《数据结构课程设计-表达式求值【完整版】.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-表达式求值【完整版】.docx（17页珍藏版）》请在课桌文档上搜索。
1、XXXXXX大学数据结构课程设计报告班级：学号：姓名：指导老师:-算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数(OPerand)、运算符(OPeratOr)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符，如：#(7+15)*(23-28/4)引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能(1)从键盘读入一个合法的算术表达式，输出正确
2、的结果。(2)显示输入序列和栈的变化过程。三、程序运行平台VisualC+6.0版本四、数据结构本程序的数据结构为栈。(1)运算符栈局部：structSqStack定义栈(char*base;栈底指针char*top;栈顶指针intstacksize;栈的长度intInitStack(SqStack&s)建立一个空栈S(if(!(s.base=(char*)malloc(50*sizeof(char)exit(O);s.top=s.base;s.stacksize=50;returnOK;charGetTop(SqStacks,char&e)运算符取栈顶元索if(s.top=s.base)栈为
3、空的时候返回ERROR(Printf(运算符栈为空!n);returnERROR;)elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;intPush(SqStack&s,chare)运算符入栈if(s.top-s.base=s.stacksize)(Printf(运算符栈满!n)；s.base=(char*)realloc(s.base,(s.stacksize+5)*sizeof(char);栈满的时候，追力口5个存储空间if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stac
4、ksize+=5;*(s.top)+=e;把e入栈returnOK;)intPo(SqStack&s,char&e)运算符出栈(if(s.top=s.base)栈为空栈的时候，返回ERROR(Printf(运算符栈为空!行)；returnERROR;else(e=*-s.top;栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;intStackTraverse(SqStack&s)/运算符栈的遍历(char*t;t=s.base;if(s.top=s.base)(Printf(“运算符栈为空!n“)；栈为空栈的时候返回ERRORreturnERROR;while(t!=
5、s.top)(printf(,%c,*t);栈不为空的时候依次取出栈内元素t+；)returnERROR;(2)数字栈局部：structSqStackn定义数栈int*base;栈底指针i11t*top;栈顶指针intstacksize;栈的长度；intInitStackn(SqStackn&s)建立一个空栈S(s.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);存储分配失败s.top=s.base;s.stacksize=50;returnOK;intGetTopn(SqStackns,int&e)数栈取栈顶元素if(s.
6、top=s.base)(Prirltf(“运算数栈为空!r);栈为空的时候返回ERRORreturnERROR;)elsee=*(stoP-1);栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;intPushn(SqStackn&s,inte)数栈入栈(if(s.top-s.base=s.stacksize)(Printf(运算数栈满!n);栈满的时候，追加5个存储空间s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int);if(!s.base)exit(OVERFLOW);s.top=s.base+s.sta
7、cksize;插入元素e为新的栈顶元素s.stacksize+=5;)*(s.top)+=e;栈顶指针变化returnOK;)intPopn(SqStackn&s,int&e)/数栈出栈(if(s.top=s.base)(printf(运算符栈为空!n”);栈为空栈的视时候，返回ERRoRreturnERROR;else(e=*-s.top;栈不空的时候，那么删除S的栈顶元素，用e返回其值，并返回OKreturnOK;)intStackTraversen(SqStackn&s)数栈遍历int*t;t=s.base;if(s.top=s.base)(printf(运算数栈为空!r);/栈为空栈的
8、时候返回ERRORreturnERROR;while(t!=s.top)(printf(%d,*t);栈不为空的时候依次输出t+；)returnERROR;)五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个#压入运算符栈。输入一个算术表达式的字符串(以#结束)，从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个#遇到一起那么运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈intPush(SeqStack*S,cha
9、rx)入栈intPop(SeqStack*S,charx)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是消耗在输入操作。六:测试用例如下图。最终结果如下图:表达式结果是：-66继续运算请接Y/y退由程序请按N/n七、源代码第七题算术表达式求值问题描述一个算术袤达式是由操作数(OPerand)、运算符(OPeratOr)和界限符(delim计ej组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#，如：#(7+15)*(23-28/4)#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。根本要求(1)从键盘读
10、入一个合法的算术表达式，输出正确的结果。(2)显示输入序列和栈的变化过程。#include#include#include#include#include#include# defineOK1# defineERROR0# defineSTACKNIT_SIZE100/#defineSTACKINCREMENT10/=/以下定义两种栈，分别存放运算符和数字/=IIit/戋3jstructSqStack定义栈(char*base;/栈底指针char*top;栈顶指针intstacksize;栈的长度)；intInitStack(SqStack&s)建立一个空栈Sif(l(s.base=(char
11、*)malloc(50*sizeof(char)exit(O);s.top=s.base;s.stacksize=50;returnOK;)charGetTop(SqStacks,char&e)运算符取栈顶元素if(s.top=s.base)栈为空的时候返回ERRORPrintf(运算符栈为空!俏;returnERROR;)elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;)intPush(SqStack&s,chare)运算符入栈if(s.top-s.base=s.stacksize)Printf(运算符栈满!n”)；s.base=(
12、char*)realloc(s.base,(s.stacksize+5)*sizeof(char);栈满的时候，追加5个存储空间if(s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;)*(s.top)+=e;把e入栈returnOK;)intPop(SqStack&s,char&e)运算符出栈(if(s.top=s.base)栈为空栈的时候，返回ERRoR(Printf(运算符栈为空!n)returnERROR;)elsee=*-s.top;栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;)i
13、ntStackTraverse(SqStack&s)运算符栈的遍历char*t;t=s.base;if(s.top=s.base)Printf(“运算符栈为空!n”)；栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)printf(%c,*t);栈不为空的时候依次取出栈内元素t+；)returnERROR;)y*-P*structSqStackn定义数栈int int int)；*base;栈底指针*top;栈顶指针stacksize;栈的长度intInitStackn(SqStackn&s)/建立一个空栈Ss.base=(int*)malloc(50*size
14、of(int);if(!s.base)exit(OVERFLOW);存储分配失败s.top=s.base;s.stacksize=50;returnOK;)intGetTopn(SqStackns,int&e)数栈取栈顶元素if(s.top=s.base)Primf(运算数栈为空!n);栈为空的时候返回ERRORreturnERROR;)elsee=*(s.top1);栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;)intPushn(SqStackn&s,inte)数栈入栈if(s.top-s.base=s.stacksize)Printf(运算数栈满!n);/栈
15、满的时候，追加5个存储空间s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int);if(s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;/ce为新的栈顶元素s.stacksize+=5;*(s.top)+=e;栈顶指针变化returnOK;)intPop(SqStackn&s,int&e)数栈出栈if(s.top=s.base)pritf(运算符栈为空!r);/栈为空栈的视时候，返回ERRORreturnERROR;else(e=*-s.top;栈不空的时候，那么删除S的栈顶元素，用e返回其值
16、，并返回OKreturnOK;)intStackTraversen(SqStackn&s)数栈遍历int*t;t=s.base;if(s.top=s.base)(printf(,运算数栈为空!n”);栈为空栈的时候返回ERRORreturnERROR;)while(t!=s.top)printf(%d,1*t);栈不为空的时候依次输出t+；returnERROR;)=/以下定义函数/=intlsoperator(charCh)判断是否为运算符，分别将运算符和数字进入不同的栈switch(ch)case:case,j:case,*t:case7:case,(,:case):casereturn1
17、;default:return0;)intOperate(inta,charop,intb)运算操作(intresult;switch(op)(caseresult=a+b;break;case,-*:result=a-b;break;case叫result=a*b;break;case7,:result=ab;break;)returnresult;)charPrecede(charch1,charCh2)运算符优先级的比拟charp;switch(ch1)casecase,:if(ch2=,+,ch2=,-,ch2=,),ch2=T)p=;/ch1运算符的优先级小于ch2运算符elseP=
18、;break;case,*:case7:if(ch2=,(,)P=；break;if(ch2=)P=；elseif(ch2=#)printf(表达式错误!运算符不匹配!n);exit(O);)elseP=;break;caseif(ch2=,),)(printf(,表达式错误!运算符不匹配!n);exit(O);)elseif(ch2=,#*)P=；elsep=,;break;)returnp;/=/以下是求值过程/=intEvaluateExpressionO参考书p53算法3.4(inta,b,temp,answer;charch,op,e;char*str;intj=0;SqStackn
19、OPND;/OPND为运算数字栈SqStackOPTR;/OPTR为运算符栈InitStack(OPTR);Push(OPTR,T);,所以此栈底是#,因为运算符栈以#作为结束标志InitStackn(OPND);/printf(nn按任意键开始求解:nn)/ch=getch();PrintfCn请输入表达式并以#结束:n“)；str=(char*)malloc(50*sizeof(char);gets(str);ch=str;Ch是字符型的，而e是整型的整数j+；GetTop(OPTRse);e为栈顶元素返回值while(ch!=#e!=#)(if(!Isoperator(Ch)遇到数字,转
20、换成十进制并计算temp=ch-O;将字符转换为十进制数ch=strj;j+；while(!lsoperator(ch)(temp=temp*10+ch-,O,;将逐个读入运算数的各位转化为十进制数ch=strj;j+；)Pushn(OPND,temp);)elseif(Isoperator(Ch)/判断是否是运算符,不是运算符那么进栈switch(Precede(e,ch)case,:Pop(OPTR,op);弹出最上面两个，并运算，把结果进栈Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);pritf(,nn运算符栈为：n);Stac
21、kTraverse(OPTR);printf(,n数栈为：n);StackTraversen(OPND);)else(Printf(您的输入有问题，请检查重新输入!”)；exit(O);)GetTop(OPTR,e);取出运算符栈最上面元素是否是#/whileGetTopn(OPND,answer);己输出。数字栈最上面即是最终结果returnanswer;/=/执行局部H=voidShowMenuO(printf(,nn);Printf(表达式求值系统n)；)voidQuit();voidManage()intanswer;/ShowMenu();answer=EvaluateExpress
22、ion();printf(,nn表达式结果是：%dn,answer);Quit();)voidQuit()(charch;pritfC,本次运算结束。n,);printf(继续本系统吗？nn);Printf(继续运算请按Y/y);printf(n退出程序请按N/n);printfC,nn);ch=getch();ch=toupper(ch);将ch字符转换成大写字母if(ch=,N,)(printf(nn系统退出。n,);exit(O);Manage();intmain()(ShowMenu();Manage();return0;感想体会与总结好的算法+编程技巧+高效率=好的程序。1、做什么都
23、需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比拟容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一局部马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做工程是这样，过我们的生活更是应该这样。3、感觉一开始设计结构写函数表达的是数据结构的思想，后面的调试那么更加表达了人的综合素质，专业知识、坚决耐心、锲而不舍，真的缺一不可啊。4、通过这次课设，不仅仅复习了C语言相关知识、稳固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。
