数据结构算术表达式求值

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