《数据结构与算法设计》实验报告——实验二学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固栈的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言实现栈的抽象数据类型，实现栈的建立、进栈、出栈、取数据等基本操作；4.用C语言实现判断运算符优先级、表达式求值等基本操作；5.理论知识与实际问题相结合，利用上述基本操作实现简单计算器。二、实验内容1、简单计算器。请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14输入：(4+2)*(2-10)=输出：-48三、程序设计1、概要设计为实现上述程序功能，应用栈存储运算符和操作数，为此需要建立一个抽象数据类型：栈。（1）、栈的抽象数据类型定义为：ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={
|ai∈D,i=1,2,……,n}基本操作：InitStack(&S)操作结果：创建一个空栈S。Push(&S,e)初始条件：栈S已存在操作结果：插入运算符e作为新的栈顶元素GetTop(&S)初始条件：栈S已存在且非空操作结果：用e返回寄存运算符栈S的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除寄存运算符栈S的栈顶元素Operate(a,theta,b)初始条件：a，b为整数，theta为运算符操作结果：返回a与b运算的结果Precede(d,c)初始条件：d，c为运算符操作结果：若d优先级大于c,返回‘>’；若d优先级小于c,返回‘<’；若d优先级等于c,返回‘=’；EvaluateExpression()初始条件：输入合法的表达式操作结果：返回表达式的值}ADTStack⑵主程序流程调用EvaluateExpression()函数计算表达式的值，并将结果输出在屏幕上。⑶各函数模块的调用关系先由主函数调用计算求值函数；再由求值模块调用栈构造函数，构造两个栈分别用来保存操作数和运算符，然后根据情况多次调用进栈、出栈、取栈顶元素、判断运算符优先级、计算表达式的值等多个函数，计算并返回表达式的值；最后由主函数在屏幕上输出表达式的结果。⑷流程图2、详细设计(1)、宏定义#defineSTACK_INIT_SIZE10//栈存储空间的初始分配量开始'='作为运算符栈的栈底元素字符c!='='|GetTop1(OPTR)!='='?c=='+'||c=='-'||c=='*'||c=='/'||c=='^'||c=='('||c==')'||c=='='?case’<’:操作符入栈case’=’:符号出栈case’>’:操作数栈栈顶2个数运算输入c结束c进入操作数栈返回运算结果输出运算结果YYN#defineSTACKINCREMENT10//空间的分配增量#defineOK1//正确时返回值为真#defineERROR0//出错时返回值为假（2）、抽象数据类型定义typedefcharElemType1;//定义元素类型1为chartypedefintElemType2;//定义元素类型2为inttypedefstruct{//栈SqStack1存储元素为charElemType1*base;//栈空间基址ElemType1*top;//栈顶指针intstacksize;//当前分配的栈空间大小}SqStack1;typedefstruct{//栈SqStack2存储元素为intElemType2*base;//栈空间基址ElemType2*top;//栈顶指针intstacksize;//当前分配的栈空间大小}SqStack2;（3）、操作算法程序实现：intInitStack1(SqStack1&S){//构造一个空栈SS.base=(ElemType1*)malloc(STACK_INIT_SIZE*sizeof(ElemType1));//为顺序栈动态分配存储空间if(!S.base)exit(OVERFLOW);//分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack1intPush1(SqStack1&S,ElemType1e){//将元素e插入栈中，使其成为新的栈顶元素if(S.top-S.base>=S.stacksize)//若栈满则追加存储空间{S.base=(ElemType1*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType1));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//元素e插入栈顶，后修改栈顶指针returnOK;//*S.top=e;S.top++;}//Push1charGetTop1(SqStack1S){//取栈顶元素并返回其值ElemType1e;if(S.top==S.base)returnERROR;//栈空e=*(S.top-1);returne;}//GetTop1intPop1(SqStack1&S,ElemType1&e)...
