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

《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：____学号：__姓名：_____一、实验目的1、熟悉VC环境，学习使用C语言实现栈的存储结构。2、通过编程、上机调试，进一步理解栈的基本概念。3、锻炼动手编程，独立思考的能力。二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。例如，输入：4+2*5=输出：14输入：(4+2)*(2-10)=输出：-48三、程序设计1、概要设计为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。(1)、栈的抽象数据类型定义为：ADTStack{数据对象：D={|,1,2,,,0}iiaaElemSetinn数据关系：R1=11{,|,,2,,}iiiiaaaaDin约定na端为栈顶，1a端为栈底。基本操作：InitStack(&S)操作结果：创建一个空栈S。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素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(2)、宏定义#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-2#defineOK1#defineERROR0#defineTRUE1#defineFALSE0(3)、主程序流程首先定义char型数组，将输入的表达式存入。随后调用EvaluateExpression(expression)函数计算结果，最后输出在屏幕上。(4)、模块调用关系：由主函数模块调用输入模块与求值模块。求值模块调用表达式转化模块与表达式求职模块，计算并返回表达式的值。最后主程序调用输出模块输出结果。(5)、流程图2、详细设计(1)、数据类型设计typedefstruct{char*base;char*top;intstacksize;开始输入表达式charc=表达式首字符c!='='||GetTop1(OPTR)!='='!In(c,OP)c存入数组;c=*(++ex);In(c,OP)数组中的数压入栈内;指针指向数组首元素case'':符号进栈c=*(++ex);case'=':符号出栈c=*(++ex);case'':操作数栈前2个数运算returnGetTop2(OPND)输出result结束}SqStack1;//定义运算符栈数据类型typedefstruct{int*base;int*top;intstacksize;}SqStack2;//定义操作数栈数据类型SqStack1OPTR;//声明运算符栈SqStack2OPND;//声明操作数栈(2)、操作算法设计StatusInitStack1(SqStack1&S){//构造运算符栈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=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-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.base=(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(SqStack2&S,int&e){//删除表达式栈的栈顶元素并用e返回if(S.top==S.base)returnERROR;//栈空e=*--S.top;returnOK;}//Pop2StatusIn(intm,chara[]){//判断m若是运算符，返回TRUE，否则返回FALSEfor(intn=0;a[n]!='\0';n++)if(m==a[n])returnTRUE;returnFALSE;}//IncharPrecede(charm,charn){//判断m与n的优先级switch(m){case'+':case'-':if(n=='+'||n=='-'||n==')'||n=='=')return'';elsereturn'';break;case'*':case'/':case'^':case'%':if(n=='(')return'';elsereturn'';break;case'(':if(n==')')return'=';elseif(n=='=')returnERROR;elsereturn'';break;case')':if(n=='(')returnERROR;elsereturn'';break;case'=':if(n=='=')return'=';elseif(n==')')returnERROR;elsereturn'';break;default:returnERROR;break;//其他情况，表达式有误}}//PrecedeintOperation(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'^':returnpow(a,b);break;default:returnERROR;break;}}//OperationintEvaluateExpression(charp[]){//主要操作函数inta,b,t;charx,theta,temp[10];char*num=temp;char*ex=p;//声明指针InitStack1(OPTR);Push1(OPTR,'=');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,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;charexpression[100];//声明表达式数组printf(Pleaseinputtheexpression:);gets(expression);//输入数组result=EvaluateExpression(expression);printf(theresultis:%d\n,result);//输出结果return0;}四、程序调试分析1、开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。于是换为gets函数，将表达式作为整体存入数组中待处理。2、第一个问题解决后，出现了第二个问题：数据结构混乱。由于gets函数得到的是char型，直接存入操作数栈后，以ASCII码形式存入，使得编译通过但运行结果错误。后来分析原因后，引入暂存数组，利用atoi函数，将数组中的数转化为整型，解决了这一问题。3、在设计主要处理函数时，出现了多次编译错误。后发现是由于指针指向混乱造成。这主要是自己的思路不清，导致程序混乱。后仔细绘制了流程图，详尽的分析了过程后，解决了该问题。五、用户使用说明1、本程序的运行环境为DOS操作系统，执行文件为：Josegh.exe。2、进入程序后，在Pleaseinputtheexpression:后输入待求表达式，以“=”结尾，并敲回车。3、程序运行后即在屏幕上输出计算结果。六、程序运行结果1、2、七、程序清单#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-2#defineOK