《数据结构》算术表达式求值

《《数据结构》算术表达式求值》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课程设计——排序算法比较、表达式求值二课程设计2——算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”

2、求算术表达式的值。二、程序的主要功能（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。三、程序运行平台VisualC++6.0版本四、数据结构本程序的数据结构为栈。（1）运算符栈部分：structSqStack//定义栈{char*base;//栈底指针char*top;//栈顶指针intstacksize;//栈的长度};-16-数据结构课程设计——排序算法比较、表达式求值intInitStack(SqStack&s)//建立一个空栈S{if(!(s.base=(char*)m

3、alloc(50*sizeof(char))))exit(0);s.top=s.base;s.stacksize=50;returnOK;}charGetTop(SqStacks,char&e)//运算符取栈顶元素{if(s.top==s.base)//栈为空的时候返回ERROR{printf("运算符栈为空!");returnERROR;}elsee=*(s.top-1);//栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;}intPush(SqStack&s,chare)//运算符入

4、栈{if(s.top-s.base>=s.stacksize){printf("运算符栈满!");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.to

5、p==s.base)//栈为空栈的时候，返回ERROR{printf("运算符栈为空!");returnERROR;}else{-16-数据结构课程设计——排序算法比较、表达式求值e=*--s.top;//栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;}}intStackTraverse(SqStack&s)//运算符栈的遍历{char*t;t=s.base;if(s.top==s.base){printf("运算符栈为空!");//栈为空栈的时候返回ERRORreturnERRO

6、R;}while(t!=s.top){printf("%c",*t);//栈不为空的时候依次取出栈内元素t++;}returnERROR;}（2）数字栈部分：structSqStackn//定义数栈{int*base;//栈底指针int*top;//栈顶指针intstacksize;//栈的长度};intInitStackn(SqStackn&s)//建立一个空栈S{s.base=(int*)malloc(50*sizeof(int));if(!s.base)exit(OVERFLOW);//存储分配失败s.top=

7、s.base;s.stacksize=50;returnOK;}intGetTopn(SqStackns,int&e)//数栈取栈顶元素{if(s.top==s.base){printf("运算数栈为空!");//栈为空的时候返回ERRORreturnERROR;}-16-数据结构课程设计——排序算法比较、表达式求值elsee=*(s.top-1);//栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;}intPushn(SqStackn&s,inte)//数栈入栈{if(s.top-s

8、.base>=s.stacksize){printf("运算数栈满!");//栈满的时候，追加5个存储空间s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;//插入元素e为新的