北理工数据结构实验报告2

《北理工数据结构实验报告2》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：____学号：__姓名：_____一、实验目的1、熟悉VC环境，学习使用C语言实现栈的存储结构。2、通过编程、上机调试，进一步理解栈的基本概念。3、锻炼动手编程，独立思考的能力。二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算

2、过程中出现小数也只取整进行计算。例如，输入：4+2*5=输出：14输入：(4+2)*(2-10)=输出：-48三、程序设计1、概要设计为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。(1)、栈的抽象数据类型定义为：ADTStack{数据对象：D=数据关系：R1=约定端为栈顶，端为栈底。基本操作：InitStack(&S)操作结果：创建一个空栈S。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操

3、作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。In(m,a[])操作结果：若m是运算符，返回TRUE。Precede(m,n)初始条件：m，n为运算符。操作结果：若m优先级大于n，返回>，反之亦然。Operation(a,theta,b)初始条件：a，b为整数，theta为运算符。操作结果：返回a与b运算的结果。EvaluateExpression(p[])初始条件：输入合法的表达式。操作结果：返回表达式的值。}ADTStack(

4、2)、宏定义#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-2#defineOK1#defineERROR0#defineTRUE1#defineFALSE0(3)、主程序流程首先定义char型数组，将输入的表达式存入。随后调用EvaluateExpression(expression)函数计算结果，最后输出在屏幕上。(4)、模块调用关系：由主函数模块调用输入模块与求值模块。求值模块调用表达式转化模块与表达式求职模块，计算并返回表

5、达式的值。最后主程序调用输出模块输出结果。(5)、流程图开始输入表达式charc=表达式首字符c!='='

6、

7、GetTop1(OPTR)!='='!In(c,OP)c存入数组;c=*(++ex);In(c,OP)数组中的数压入栈内;指针指向数组首元素case'<':符号进栈c=*(++ex);case'=':符号出栈c=*(++ex);case'>':操作数栈前2个数运算returnGetTop2(OPND)输出result结束2、详细设计(1)、数据类型设计typedefstruct{char*base;c

8、har*top;intstacksize;}SqStack1;//定义运算符栈数据类型typedefstruct{int*base;int*top;intstacksize;}SqStack2;//定义操作数栈数据类型SqStack1OPTR;//声明运算符栈SqStack2OPND;//声明操作数栈(2)、操作算法设计StatusInitStack1(SqStack1&S){//构造运算符栈S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));//申请空间if

9、(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack1StatusInitStack2(SqStack2&S){//构造操作数栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));//申请空间if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_

10、SIZE;returnOK;}//InitStack2charGetTop1(SqStack1S){//取得运算符栈的栈顶元素chare;if(S.top==S.base)returnERROR;//栈空e=*(S.top-1);returne;}//GetTop1intGetTop2(SqStack2S){//取得操作数栈的栈顶元素inte;if(S.top==S.base)returnERROR