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

二课程设计2——算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。三、程序运行平台VisualC++6.0版本四、数据结构本程序的数据结构为栈。（1）运算符栈部分：structSqStack//定义栈{char*base;//栈底指针char*top;//栈顶指针intstacksize;//栈的长度};数据结构课程设计——排序算法比较、表达式求值-2-intInitStack(SqStack&s)//建立一个空栈S{if(!(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)//栈为空的时候返回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.stacksize+=5;}*(s.top)++=e;//把e入栈returnOK;}intPop(SqStack&s,char&e)//运算符出栈{if(s.top==s.base)//栈为空栈的时候，返回ERROR{printf(运算符栈为空!\n);returnERROR;}else{数据结构课程设计——排序算法比较、表达式求值-3-e=*--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;}（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=s.base;s.stacksize=50;returnOK;}intGetTopn(SqStackns,int&e)//数栈取栈顶元素{if(s.top==s.base){printf(运算数栈为空!\n);//栈为空的时候返回ERRORreturnERROR;}数据结构课程设计——排序算法比较、表达式求值-4-elsee=*(s.top-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.stacksize;//插入元素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(运算数栈为空!\n);//栈为空栈的时候返回ERRORreturnERROR;}while(t!=s.top){数据结构课程设计——排序算法比较、表达式求值-5-printf(%d,*t);//栈不为空的时候依次输出t++;}returnERROR;}五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个‘#’压入运算符栈。输入一个算术表达式的字符串（以‘#’结束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个‘#’遇到一起则运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：O(n)数据压缩存储栈，其操作主要有：建立栈intPush(SeqStack*S,charx)入栈intPop(SeqStack*S,charx)出栈。以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在输入操作。六、测试用例如图所示。数据结构课程设计——排序算法比较、表达式求值-6-最终结果如图所示：七、源代码/**************************************************************************************************第七题算术表达式求值[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。***************************************************************************************************/#includestdio.h#includestring.h数据结构课程设计——排序算法比较、表达式求值-7-#includestdlib.h#includemath.h#includeconio.h#includectype.h#defineOK1#defineERROR0#defineSTACK_INIT_SIZE100//#defineSTACKINCREMENT10//========================================================//以下定义两种栈，分别存放运算符和数字//========================================================//*******************运算符栈部分*************************structSqStack//定义栈{char*base;//栈底指针char*top;//栈顶指针intstacksize;//栈的长度};intInitStack(SqStack&s)//建立一个空栈S{if(!(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)//栈为空的时候返回ERROR{printf(运算符栈为空!\n);returnERROR;}elsee=*(s.top-1);//栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;数据结构课程设计——排序算法比较、表达式求值-8-}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.stacksize+=5;}*(s.top)++=e;//把e入栈returnOK;}intPop(SqStack&s,char&e)//运算符出栈{if(s.top==s.base)//栈为空栈的时候，返回ERROR{printf(运算符栈为空!\n);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!=s.top)数据结构课程设计——排序算法比较、表达式求值-9-{printf(%c,*t);//栈不为空的时候依次取出栈内元素t++;}returnERROR;}//**********************数字栈部分***************************structSqStackn//定义数栈{int*base;//栈底指针int*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.top==s.base){printf(运算数栈为空!\n);//栈为空的时候返回ERRORreturnERROR;}elsee=*(s.top-1);//栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;}intPushn(SqStackn&s,inte)//数栈入栈{if(s.top-s.base=s.s