北理工数据结构实验报告

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

2、8三、程序设计1 、概要设计为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。(1) 、栈的抽象数据类型定义为：ADTStack数据对象：D=ai|aiElemSet,i1,2,K,n,n0数据关系：R1=ai1,ai|ai1,aiD,i2,K,n约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：创建一个空栈S。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)

3、初始条件：栈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(2) 、宏定义# defineSTACK_INIT_SIZE100# defineSTACKINCREMENT10# defineOVERFLO

4、W-2# defineOK1# defineERROR0# defineTRUE1# defineFALSE0(3) 、主程序流程首先定义char型数组，将输入的表达式存入。随后调用EvaluateExpression(expression)函数计算结果，最后输出在屏幕上。(4) 、模块调用关系：由主函数模块调用输入模块与求值模块。求值模块调用表达式转化模块与表达式求职模块，计算并返回表达式的值。最后主程序调用输出模块输出结果。(5) 、流程图开始输入表达式char c=表达式首字符case '<':符号进 栈 c=*（+ex）; case '=':符号出

5、 栈 c=*（+ex）;case '>':操作数 栈前2个数运算return GetTop2(OPND)结束2、详细设计（1）、数据类型设计typedefstructchar*base;char*top;intstacksize;SqStack1;typedefstructint*base;/ 定义运算符栈数据类型int*top;intstacksize;SqStack2;/定义操作数栈数据类型SqStack1OPTR;/声明运算符栈SqStack2OPND;/声明操作数栈(2) 、操作算法设计StatusInitStack1(SqStack1&S)/构造运算符栈

6、S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/申请空间if(!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=

7、STACK_INIT_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;/栈空e=*(S.top-1);returne;/GetTop2StatusPush1(SqStack1&S,chare)/插入元素e为运算符栈的栈顶元素栈满，追加存储空间if(S.top

8、-S.base>=S.stacksize)/S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;/Push1StatusPush2(SqStack2&S,inte)/插入元素e为操作数栈的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.b

9、ase=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;/Push2StatusPop1(SqStack1&S,char&e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base)returnERROR;/栈空e=*-S.top;returnOK;/Pop1StatusPop2(SqS

10、tack2&S,int&e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base)returnERROR;/栈空e=*-S.top;returnOK;/Pop2StatusIn(intm,chara)/判断m若是运算符，返回TRUE，否则返回FALSEfor(intn=0;an!='0'n+)if(m=an)returnTRUE;returnFALSE;/IncharPrecede(charm,charn)/判断m与n的优先级switch(m)case'+':case'-':if(n='+'|n=

11、9;-'|n=')'|n='=')returnelsereturn'<'break;case'*':case'/':case、case'%':if(n='(')returnelsereturn'>'break;case'C：if(n=')')returnelseif(n='=')returnERROR;elsereturn'<'break;case')':if(n=

12、9;(')returnERROR;elsereturn'>'break;caseif(n='=')return'='elseif(n=')')returnERROR;elsereturn'<'break;default:returnERROR;break;/其他情况，表达式有误/PrecedeintOperation(inta,chartheta,intb)/运算函数switch(theta)case'+':returna+b;break;case'-':retu

13、rna-b;break;case'*':returna*b;break;case'/':returna/b;break;case'%':returna%b;break;case'A':returnpow(a,b);break;default:returnERROR;break;/OperationintEvaluateExpression(charp)/主要操作函数inta,b,t;charx,theta,temp10;char*num=temp;char*ex=p;/声明指针InitStack1(OPTR);Push1(OPTR

14、,'=');InitStack2(OPND);charc=*p;while(c!='='|GetTop1(OPTR)!='=')if(!In(c,OP)/不是运算符进数组*(num+)=c;c=*(+ex);if(In(c,OP)/是运算符将数组压入栈*num='0't=atoi(temp);/将temp数组转化为整型数num=temp;/指针指回数组头元素Push2(OPND,t);elseswitch(Precede(GetTop1(OPTR),c)case'<':/栈顶元素优先级低Push1(OPTR,

15、c);c=*(+ex);break;case'=':/脱括号并接受下一字符Pop1(OPTR,x);c=*(+ex);break;case'>':/运算并将结果入栈Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operation(a,theta,b);break;returnGetTop2(OPND);返回操作数栈顶元素/EvaluateExpression(3) 、主函数设计intmain()/主函数intresult;charexpression100;/声明表达式数组printf(&quo

16、t;Pleaseinputtheexpression:");gets(expression);/输入数组result=EvaluateExpression(expression);printf("theresultis:%dn",result);/输出结果return0;四、程序调试分析1 、开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。于是换为gets函数，将表达式作为整体存入数组中待处理。2、第一个问题解决后，出现了第二个问题：数据结构混乱。由于gets函数得到的是char型，直接存入操作数栈后，以

17、ASCII码形式存入，使得编译通过但运行结果错误。后来分析原因后，引入暂存数组，利用atoi函数，将数组中的数转化为整型，解决了这一问题。3、在设计主要处理函数时，出现了多次编译错误。后发现是由于指针指向混乱造成。这主要是自己的思路不清，导致程序混乱。后仔细绘制了流程图，详尽的分析了过程后，解决了该问题。五、用户使用说明1、本程序的运行环境为DOS操作系统，执行文件为：Josegh.exe。2、进入程序后，在Pleaseinputtheexpression:后输入待求表达式，以“二”结尾，弁敲回车。3、程序运行后即在屏幕上输出计算结果。六、程序运行结果1、2、七、程序清单#defineSTAC

18、K_INIT_SIZE100# defineSTACKINCREMENT10# defineOVERFLOW-2# defineOK1# defineERROR0# defineTRUE1#defineFALSE0#include"stdio.h"#include"stdlib.h"#include"math.h"typedefintStatus;charOP尸'+','-','*'/'(',')>','','='/定

19、义运算符数组typedefstructchar*base;char*top;intstacksize;SqStack1;/定义运算符栈数据类型typedefstructint*base;int*top;intstacksize;SqStack2;/定义操作数栈数据类型SqStack1OPTR;/声明运算符栈SqStack2OPND;/声明操作数栈StatusInitStack1(SqStack1&S)/构造运算符栈S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/申请空间if(!S.base)exit(OVERFLOW);/存储分配失

20、败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;StatusInitStack2(SqStack2&S)/构造操作数栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);/申请空间if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;charGetTop1(SqStack1S)/取得运算符栈的栈顶元素chare;if(S.top=S.base)returnERROR;/栈空e=*

21、(S.top-1);returne;intGetTop2(SqStack2S)/取得操作数栈的栈顶元素inte;if(S.top=S.base)returnERROR;/栈空e=*(S.top-1);returne;StatusPush1(SqStack1&S,chare)/插入元素e为运算符栈的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base)exit(OVERFLOW);/存储分

22、配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;StatusPush2(SqStack2&S,inte)/插入元素e为操作数栈的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacks

23、ize+=STACKINCREMENT;*S.top+=e;returnOK;StatusPop1(SqStack1&S,char&e)栈空/删除表达式栈的栈顶元素并用e返回if(S.top=S.base)returnERROR;/e=*-S.top;returnOK;StatusPop2(SqStack2&S,int&e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base)returnERROR;/栈空e=*-S.top;returnOK;StatusIn(intm,chara)/判断m若是运算符，返回TRUE，否则返回FALSEfor(intn

24、=0;an!='0'n+)if(m=an)returnTRUE;returnFALSE;charPrecede(charm,charn)/判断m与n的优先级switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return'>'elsereturn'<'break;case'*':case'/':case、case'%':if(n='(

25、')return'<'elsereturn'>'break;case'(':if(n=')')return'='elseif(n='=')returnERROR;elsereturn'<'break;case')':if(n='(')returnERROR;elsereturn'>'break;case'=':if(n='=')return'='elseif

26、(n=')')returnERROR;elsereturn'<'break;default:returnERROR;break;/其他情况，表达式有误intOperation(inta,chartheta,intb)/运算函数switch(theta)case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':returna/b;break;case'%':returna%b;break;case'A':returnpow(a,b);bre