数据结构课程设计-表达式求值

1、第第 页共18页数据结构课程设计一一表达式求值数据结构课程设计一一表达式求值第第7页共18页建立栈intPush(SeqStack*S,charx)入栈intPop(SeqStack*S,charx)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是耗费在输入操作。六、测试用例最终结果如图所示:七、源代码/*第七题算术表达式求值问题描述一个算术表达式是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表

2、达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。*/#include#include#include#include#include#include#defineOK1#defineERROR0#defineSTACK_INIT_SIZE100/#defineSTACKINCREMENT10/=/以下定义两种栈，分别存放运算符和数字/=structSqStack/定义栈/*运算符栈部分/*运算符栈部分*char*base;/栈底指针char*top;/栈顶指针intstacksi

3、ze;/栈的长度;intInitStack(SqStack&s)/建立一个空栈Sif(!(s.base=(char*)malloc(50*sizeof(char)exit(0);s.top=s.base;s.stacksize=50;returnOK;charGetTop(SqStacks,char&e)/运算符取栈顶元素if(s.top=s.base)/栈为空的时候返回ERRORprintf(运算符栈为空!n);returnERROR;elsee=*(s.top-1);/栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;intPush(SqStack&s,chare)

4、/运算符入栈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.stacksize+=5;*(s.top)+=e;/把e入栈returnOK;intPop(SqStack&s,char&e)/运算符出栈if(s.top=s.base)/栈为空栈的时候，返回ERRORprintf(运算符栈为空!n);retu

5、rnERROR;elsee=*-s.top;/栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;intStackTraverse(SqStack&s)/运算符栈的遍历char*t;t=s.base;if(s.top=s.base)printf(运算符栈为空!n);栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)printf(%c,*t);/栈不为空的时候依次取出栈内元素t+;returnERROR;/*数字栈部分*/*数字栈部分*structSqStackn/定义数栈int*base;/栈底指针int*top;/栈顶指针intstack

6、size;/栈的长度;intInitStackn(SqStackn&s)/建立一个空栈Ss.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.top=s.base)printf(运算数栈为空!n);/栈为空的时候返回ERRORreturnERROR;elsee=*(s.top-1);栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;in

7、tPushn(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.stacksize;/插入元素e为新的栈顶元素s.stacksize+=5;*(s.top)+=e;/栈顶指针变化returnOK;intPopn(SqStackn&s,int&e)/数栈出栈if(s.top=s.base)prin

8、tf(运算符栈为空!n);/栈为空栈的视时候，返回ERRORreturnERROR;elsee=*-s.top;/栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OKreturnOK;intStackTraversen(SqStackn&s)/数栈遍历int*t;t=s.base;if(s.top=s.base)printf(运算数栈为空!n);/栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)printf(%d,*t);/栈不为空的时候依次输出t+;returnERROR;/=/以下定义函数/=intIsoperator(charch)/判断是否为运算

9、符，分别将运算符和数字进入不同的栈switch(ch)case+:case-:case*:case/:case(:case):case#:return1;default:return0;intOperate(inta,charop,intb)/运算操作intresult;switch(op)case+:result=a+b;break;case-:result=a-b;break;case*:result=a*b;break;case/:result=a/b;break;returnresult;charPrecede(charch1,charch2)/运算符优先级的比较charp;switc

10、h(ch1)case+:case-:if(ch2=+|ch2=-|ch2=)|ch2=#)p=;/ch1运算符的优先级小于ch2运算符elsep=;break;case/:if(ch2=()p=;break;case(:if(ch2=)p=;elseif(ch2=#)printf(”表达式错误!运算符不匹配!n);exit(0);elsep=;break;case#:if(ch2=)printf(表达式错误!运算符不匹配!n);exit(0);elseif(ch2=#)p=;elsep=;break;returnp;/=/以下是求值过程/=intEvaluateExpression()参考书p

11、53算法3.4inta,b,temp,answer;charch,op,e;char*str;intj=0;SqStacknOPND;/OPND为运算数字栈SqStackOPTR;/OPTR为运算符栈InitStack(OPTR);Push(OPTR,#);/,所以此栈底是#，因为运算符栈以#作为结束标志InitStackn(OPND);/printf(”nn按任意键开始求解:nn”)；/ch=getch();printf(n请输入表达式并以#结束:n);str=(char*)malloc(50*sizeof(char);gets(str);ch=strj;ch是字符型的，而e是整型的整数j+

12、;GetTop(OPTR,e);/e为栈顶元素返回值while(ch!=#|e!=#)if(!Isoperator(ch)/遇到数字,转换成十进制并计算temp=ch-0;/将字符转换为十进制数ch=strj;j+;while(!Isoperator(ch)temp=temp*10+ch-0;/将逐个读入运算数的各位转化为十进制数ch=strj;j+;Pushn(OPND,temp);elseif(Isoperator(ch)/判断是否是运算符,不是运算符则进栈switch(Precede(e,ch)case:Pop(OPTR,op);/弹出最上面两个，并运算，把结果进栈Popn(OPND,b

13、);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf(”nn运算符栈为：n”)；StackTraverse(OPTR);printf(n数栈为：n)；StackTraversen(OPND)；elseprintf(”您的输入有问题，请检查重新输入!)；exit(0)；GetTop(OPTR,e)；/取出运算符栈最上面元素是否是#/whileGetTopn(OPND,answer)；/已输出。数字栈最上面即是最终结果returnanswer；/=/执行部分/=voidShowMenu()printf(nn)；printf(”表达式求值系统n”)；voi

14、dQuit()；voidManage()intanswer；/ShowMenu()；answer=EvaluateExpression()；printf(nn表达式结果是:%dn,answer)；Quit()；voidQuit()charch；printf(本次运算结束。n”)；printf(”继续本系统吗？nn”)；printf(继续运算请按Y/y);printf(n退出程序请按N/n);printf(n_n);ch=getch();ch=toupper(ch);将ch字符转换成大写字母if(ch=N)printf(nn系统退出。n”)；exit(0);Manage();intmain()ShowMenu();Manage();return0;感想体会与总结好的算法+编程技巧+高效率=好的程序。1、做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程