北理工数据结构实验报告

《数据结构与算法设计》

实验报告

——实验二

学院：自动化学院 班级：____ 学号：__ 姓名：_____

一、实验目的

完美WORD格式编辑

专业资料整理分享

1、熟悉VC环境，学习使用C语言实现栈的存储结构。 2、通过编程、上机调试，进一步理解栈的基本概念。 3、锻炼动手编程，独立思考的能力。 二、实验内容

实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、（）和=：

① 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；

② 输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 1、概要设计

为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。 (1)、栈的抽象数据类型定义为： ADT Stack{

数据对象：D={ai|aiElemSet,i1,2,,n,n0}

数据关系：R1={ai1,ai|ai1,aiD,i2,,n} 约定an端为栈顶，a1端为栈底。

完美WORD格式编辑

专业资料整理分享

基本操作： 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[]) 初始条件：输入合法的表达式。

完美WORD格式编辑

专业资料整理分享

操作结果：返回表达式的值。 }ADT Stack (2)、宏定义

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 (3)、主程序流程

首先定义char型数组，将输入的表达式存入。随后调用EvaluateExpression(expression)函数计算结果，最后输出在屏幕上。

(4)、模块调用关系：

由主函数模块调用输入模块与求值模块。

求值模块调用表达式转化模块与表达式求职模块，计算并返回表达式的值。最后主程序调用输出模块输出结果。 (5)、流程图 开始 完美WORD格式编辑 输入表达式 char c=表达式首字符 专业资料整理分享

2、详细设计

(1)、数据类型设计 typedef struct{ char *base; char *top; int stacksize;

}SqStack1; //定义运算符栈数据类型

完美WORD格式编辑

专业资料整理分享

typedef struct{ int *base; int *top; int stacksize;

}SqStack2; //定义操作数栈数据类型 SqStack1 OPTR; //声明运算符栈 SqStack2 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; }//InitStack1

Status InitStack2(SqStack2 &S){ //构造操作数栈

S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); //申请空间

完美WORD格式编辑

专业资料整理分享

if(!S.base)exit(OVERFLOW); //存储分配失败 S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack2

char GetTop1(SqStack1 S){ //取得运算符栈的栈顶元素 char e;

if(S.top==S.base) return ERROR; //栈空 e=*(S.top-1); return e; }//GetTop1

int GetTop2(SqStack2 S){ //取得操作数栈的栈顶元素 int e;

if(S.top==S.base) return ERROR; //栈空 e=*(S.top-1); return e; }//GetTop2

Status Push1(SqStack1 &S,char e){ //插入元素e为运算符栈的栈顶元素

if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

完美WORD格式编辑

专业资料整理分享

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

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; }//Push2

完美WORD格式编辑

专业资料整理分享

Status Pop1(SqStack1 &S,char &e){ //删除表达式栈的栈顶元素并用e返回 if(S.top==S.base) return ERROR; //栈空 e=*--S.top; return OK; }//Pop1

Status Pop2(SqStack2 &S,int &e){ //删除表达式栈的栈顶元素并用e返回 if(S.top==S.base) return ERROR; //栈空 e=*--S.top; return OK; }//Pop2

Status In(int m,char a[]){

//判断m若是运算符，返回TRUE，否则返回FALSE for(int n=0;a[n]!='\\0';n++) if(m==a[n]) return TRUE; return FALSE; }//In

char Precede(char m,char n){ //判断m与n的优先级 switch(m){ case'+':

完美WORD格式编辑

专业资料整理分享

case'-':

if(n=='+'||n=='-'||n==')'||n=='=') return '>';

else return '<';break; case'*': 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 return '>';break; case'=':

完美WORD格式编辑

专业资料整理分享

if(n=='=') return '='; else if(n==')') return ERROR; else return '<';break; default:

return ERROR;break;//其他情况，表达式有误 }

}// Precede

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'^':return pow(a,b);break; default:return ERROR;break; }

}//Operation

int EvaluateExpression(char p[]){

完美WORD格式编辑

专业资料整理分享

//主要操作函数

int a,b,t;char x,theta,temp[10]; char* num=temp;char* ex=p;//声明指针 InitStack1(OPTR);Push1(OPTR,'='); InitStack2(OPND);char c=*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); } } else

switch(Precede(GetTop1(OPTR),c)){ case '<'://栈顶元素优先级低 Push1(OPTR,c);c=*(++ex); break;

case '='://脱括号并接受下一字符 Pop1(OPTR,x);c=*(++ex);

完美WORD格式编辑

专业资料整理分享

break;

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 expression[100]; //声明表达式数组 printf(\"Please input the expression:\"); gets(expression); //输入数组

result=EvaluateExpression(expression);

printf(\"the result is :%d\\n\输出结果 return 0; }

四、程序调试分析

1、开始时，使用getchar函数输入，但其有较大的弊端，

完美WORD格式编辑

专业资料整理分享

只能输入0-9之间的整数，不能实现多位数及小数的计算。于是换为gets函数，将表达式作为整体存入数组中待处理。

2、第一个问题解决后，出现了第二个问题：数据结构混乱。由于gets函数得到的是char型，直接存入操作数栈后，以ASCII码形式存入，使得编译通过但运行结果错误。后来分析原因后，引入暂存数组，利用atoi函数，将数组中的数转化为整型，解决了这一问题。

3、在设计主要处理函数时，出现了多次编译错误。后发现是由于指针指向混乱造成。这主要是自己的思路不清，导致程序混乱。后仔细绘制了流程图，详尽的分析了过程后，解决了该问题。

五、用户使用说明

1、本程序的运行环境为DOS操作系统，执行文件为：Josegh.exe。

2、进入程序后，在Please input the expression:后输入待求表达式，以“=”结尾，并敲回车。

3、程序运行后即在屏幕上输出计算结果。 六、程序运行结果 1、

2、

完美WORD格式编辑

专业资料整理分享

七、程序清单

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define 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 struct{ char *base; char *top; int stacksize;

}SqStack1; //定义运算符栈数据类型 typedef struct{

完美WORD格式编辑

专业资料整理分享

int *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); //存储分配失败 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;

完美WORD格式编辑

专业资料整理分享

S.stacksize=STACK_INIT_SIZE; return OK; }

char GetTop1(SqStack1 S){ //取得运算符栈的栈顶元素 char e;

if(S.top==S.base) return 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));

完美WORD格式编辑

专业资料整理分享

if(!S.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); //存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }

*S.top++=e; return OK; }

Status Pop1(SqStack1 &S,char &e){ //删除表达式栈的栈顶元素并用e返回

完美WORD格式编辑

专业资料整理分享

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 In(int m,char a[]){

//判断m若是运算符，返回TRUE，否则返回FALSE for(int n=0;a[n]!='\\0';n++) if(m==a[n]) return TRUE; return FALSE; }

char Precede(char m,char n){ //判断m与n的优先级 switch(m){ case'+': case'-':

if(n=='+'||n=='-'||n==')'||n=='=')

完美WORD格式编辑

专业资料整理分享

return '>';

else return '<';break; case'*': 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 return '>';break; case'=': if(n=='=') return '=';

完美WORD格式编辑

专业资料整理分享

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'^':return pow(a,b);break; default:return ERROR;break; } }

int EvaluateExpression(char p[]){ //主要操作函数

int a,b,t;char x,theta,temp[10];

完美WORD格式编辑

专业资料整理分享

char* num=temp;char* ex=p;//声明指针 InitStack1(OPTR);Push1(OPTR,'='); InitStack2(OPND);char c=*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); } } else

switch(Precede(GetTop1(OPTR),c)){ case '<'://栈顶元素优先级低 Push1(OPTR,c);c=*(++ex); break;

case '='://脱括号并接受下一字符 Pop1(OPTR,x);c=*(++ex); break;

case '>'://运算并将结果入栈

完美WORD格式编辑

专业资料整理分享

Pop1(OPTR,theta);

Pop2(OPND,b);Pop2(OPND,a); Push2(OPND,Operation(a,theta,b)); break; } }

return GetTop2(OPND);返回操作数栈顶元素 }

int main(){ //主函数

int result;char expression[100]; //声明表达式数组 printf(\"Please input the expression:\"); gets(expression); //输入数组

result=EvaluateExpression(expression);

printf(\"the result is :%d\\n\输出结果 return 0; }

完美WORD格式编辑