北理工数据结构实验报告

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

2、三、程序设计 1、概要设计为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。(1)、栈的抽象数据类型定义为：ADT Stack数据对象：D=数据关系：R1= 约定端为栈顶，端为栈底。基本操作：InitStack(&S)操作结果：创建一个空栈S。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。In(m,a)操作结果：若

3、m是运算符，返回TRUE。Precede(m, n)初始条件：m，n为运算符。操作结果：若m优先级大于n，返回>，反之亦然。Operation(a, theta,b)初始条件：a，b为整数，theta为运算符。操作结果：返回a与b运算的结果。EvaluateExpression(p)初始条件：输入合法的表达式。操作结果：返回表达式的值。ADT Stack(2)、宏定义#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1

4、#define FALSE 0(3)、主程序流程首先定义char型数组，将输入的表达式存入。随后调用EvaluateExpression(expression)函数计算结果，最后输出在屏幕上。(4)、模块调用关系：由主函数模块调用输入模块与求值模块。求值模块调用表达式转化模块与表达式求职模块，计算并返回表达式的值。最后主程序调用输出模块输出结果。(5)、流程图开始输入表达式char c=表达式首字符c!='='|GetTop1(OPTR)!='='!In(c,OP)c存入数组;c=*(+ex);In(c,OP)数组中的数压入栈内;指针指向数组首元素case &#

5、39;<':符号进栈 c=*(+ex);case '=':符号出栈c=*(+ex);case '>':操作数栈前2个数运算return GetTop2(OPND)输出result结束 2、详细设计(1)、数据类型设计typedef structchar *base;char *top;int stacksize;SqStack1; /定义运算符栈数据类型typedef structint *base;int *top;int stacksize;SqStack2; /定义操作数栈数据类型SqStack1 OPTR; /声明运算符栈SqStac

6、k2 OPND; /声明操作数栈(2)、操作算法设计Status InitStack1(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;return OK;/InitStack1Status InitStack2(SqStack2 &S)/构造操作数栈S.base=(int *)malloc(STACK_INIT_SIZE*siz

7、eof(int);/申请空间if(!S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2char GetTop1(SqStack1 S)/取得运算符栈的栈顶元素char e;if(S.top=S.base) return ERROR; /栈空e=*(S.top-1);return e;/GetTop1int GetTop2(SqStack2 S)/取得操作数栈的栈顶元素int e;if(S.top=S.base) return ERROR; /栈空e=*(S.to

8、p-1);return e;/GetTop2Status Push1(SqStack1 &S,char e)/插入元素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;return OK;/Push1

9、Status Push2(SqStack2 &S,int e)/插入元素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;return OK;/Push2Status Pop1(SqStack1 &a

10、mp;S,char &e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base) return ERROR; /栈空e=*-S.top;return OK;/Pop1Status Pop2(SqStack2 &S,int &e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base) return ERROR; /栈空e=*-S.top;return OK;/Pop2Status In(int m,char a)/判断m若是运算符，返回TRUE，否则返回FALSEfor(int n=0;an!='0'n+)if(m=an) retu

11、rn TRUE;return FALSE;/Inchar Precede(char m,char n)/判断m与n的优先级switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return '>'else return '<'break;case'*':case'/':case'':case'%':if(n='(')return

12、 '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;else return '<'break;case')':if(n='(')return ERROR;else return '>'break;case'=':if(n='=')return '='else i

13、f(n=')')return ERROR;else return '<'break;default:return ERROR;break;/其他情况，表达式有误/ Precedeint Operation(int a,char theta,int b)/运算函数switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case&

14、#39;%':return a%b;break;case'':return pow(a,b);break;default:return ERROR;break;/Operationint EvaluateExpression(char p)/主要操作函数int a,b,t;char x,theta,temp10;char* num=temp;char* ex=p;/声明指针InitStack1(OPTR);Push1(OPTR,'=');InitStack2(OPND);char c=*p;while(c!='='|GetTop1(OPT

15、R)!='=')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);bre

16、ak;case '>':/运算并将结果入栈Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operation(a,theta,b);break;return GetTop2(OPND);返回操作数栈顶元素/ EvaluateExpression(3)、主函数设计int main()/主函数int result;char expression100; /声明表达式数组printf("Please input the expression:");gets(expression); /输入数组res

17、ult=EvaluateExpression(expression);printf("the result is :%dn",result);/输出结果return 0;四、程序调试分析 1、开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。于是换为gets函数，将表达式作为整体存入数组中待处理。2、第一个问题解决后，出现了第二个问题：数据结构混乱。由于gets函数得到的是char型，直接存入操作数栈后，以ASCII码形式存入，使得编译通过但运行结果错误。后来分析原因后，引入暂存数组，利用atoi函数，将数组中的数转

18、化为整型，解决了这一问题。3、在设计主要处理函数时，出现了多次编译错误。后发现是由于指针指向混乱造成。这主要是自己的思路不清，导致程序混乱。后仔细绘制了流程图，详尽的分析了过程后，解决了该问题。五、用户使用说明 1、本程序的运行环境为DOS操作系统，执行文件为：Josegh.exe。2、进入程序后，在Please input the expression:后输入待求表达式，以“=”结尾，并敲回车。 3、程序运行后即在屏幕上输出计算结果。六、程序运行结果 1、 2、七、程序清单#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define

19、OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#include"stdio.h"#include"stdlib.h"#include"math.h"typedef int Status;char OP='+','-','*','/','(',')','','%','=' /定义运算符数组typedef st

20、ructchar *base;char *top;int stacksize;SqStack1; /定义运算符栈数据类型typedef structint *base;int *top;int stacksize;SqStack2; /定义操作数栈数据类型SqStack1 OPTR; /声明运算符栈SqStack2 OPND; /声明操作数栈Status InitStack1(SqStack1 &S)/构造运算符栈S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/申请空间if(!S.base)exit(OVERFLOW); /存储分

21、配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status InitStack2(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;return OK;char GetTop1(SqStack1 S)/取得运算符栈的栈顶元素char e;if(S.top=S.base) return

22、 ERROR; /栈空e=*(S.top-1);return e;int GetTop2(SqStack2 S)/取得操作数栈的栈顶元素int e;if(S.top=S.base) return ERROR; /栈空e=*(S.top-1);return e;Status Push1(SqStack1 &S,char e)/插入元素e为运算符栈的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S

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

24、S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop1(SqStack1 &S,char &e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base) return ERROR; /栈空e=*-S.top;return OK;Status Pop2(SqStack2 &S,int &e)/删除表达式栈的栈顶元素并用e返回if(S.top=S.base) return ERROR; /栈空e=*-S.top;return OK;Status

25、 In(int m,char a)/判断m若是运算符，返回TRUE，否则返回FALSEfor(int n=0;an!='0'n+)if(m=an) return TRUE;return FALSE;char Precede(char m,char n)/判断m与n的优先级switch(m)case'+':case'-':if(n='+'|n='-'|n=')'|n='=')return '>'else return '<'break;cas

26、e'*':case'/':case'':case'%':if(n='(')return '<'else return '>'break;case'(':if(n=')')return '='else if(n='=')return ERROR;else return '<'break;case')':if(n='(')return ERROR;else r

27、eturn '>'break;case'=':if(n='=')return '='else if(n=')')return ERROR;else return '<'break;default:return ERROR;break;/其他情况，表达式有误int Operation(int a,char theta,int b)/运算函数switch(theta)case'+':return a+b;break;case'-':return a-b;break;case'*':return a*b;break;case'/':return a/b;break;case'%':return a%b;break;case'':