北京理工大学数据结构实验报(2).docx

《北京理工大学数据结构实验报(2).docx》由会员分享，可在线阅读，更多相关《北京理工大学数据结构实验报(2).docx（16页珍藏版）》请在三一办公上搜索。

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

2、10)= 输出：-48 三、程序设计 1、概要设计 为实现上述功能，应使用两个栈，分别寄存操作数和运算符。为此需要栈的抽象数据结构。 栈的抽象数据类型定义如下： ADT Stack 数据对象： D = ai | ai ElemSet, i=1,n，n0 数据关系： R1 = | ai-1,ai D, i=2, ,n 基本操作： InitStack1(SqStack1 &S) 操作结果：创建一个空栈S，以存储运算符 InitStack2(SqStack2 &S) 操作结果：创建一个空栈S，以存储操作数 Push1(SqStack1 &S,char e) 初始条件：栈S已存在 操作结果：插入运算符

3、e作为新的栈顶元素 Push2(SqStack2 &S,int e) 初始条件：栈S已存在 操作结果：插入操作数e作为新的栈顶元素 Precede(char d,char c) 初始条件：d，c为运算符 操作结果：若d优先级大于c,返回；若d优先级小于c,返回；若d优先级等于c,返回=； GetTop1(SqStack1 &S) 初始条件：栈S已存在且非空 操作结果：用e返回寄存运算符栈S的栈顶元素 GetTop2(SqStack2 &S) 初始条件：栈S已存在且非空 操作结果：用e返回寄存操作数栈S的栈顶元素 Pop1(SqStack1 &S,char &e) 2 初始条件：栈S已存在且非空

4、 操作结果：删除寄存运算符栈S的栈顶元素 Pop2(SqStack2 &S,int &e) 初始条件：栈S已存在且非空 操作结果：删除寄存操作数栈S的栈顶元素 Operate(int a,char theta,int b) 初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 EvaluateExpression 初始条件：输入合法的表达式 操作结果：返回表达式的值 ADT Stack 主程序流程 调用EvaluateExpression函数计算表达式的值，输出在屏幕上。 各模块的调用关系 先由主函数调用计算求值模块； 再由求值模块调用栈构造模块，表达式转换模块及表达式求

5、值模块，计算并返回表达式的值； 最后由主函数在屏幕上输出表达式的结果。 流程图 3 开始 = 作为运算符栈的栈底字符 输入c c!=|GetTop1(OPTR)!= Y c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!= N case:操作数栈栈顶2个数运算 Y c进入操作数栈 返回运算结果 输出运算结果 结束 2、详细设计 数据类型设计 typedef struct SqStack1 char * base; 4 char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct SqStack2 int *

6、base; int * top; int stacksize; SqStack2; /定义操作数栈数据类型 操作算法设计 int 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 1; int InitStack2(SqStack2 &S)/构造操作数栈 S.base=(int *)mallo

7、c(STACK_INIT_SIZE * sizeof(int); /申请存储空间 if(!S.base) exit(OVERFLOW); /存储空间分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; char GetTop1(SqStack1 &S)/取得运算符栈栈顶元素 char e; if(S.top=S.base)/栈空 return 0; e=*(S.top-1); return e; int GetTop2(SqStack2 &S) /取得操作数栈栈顶元素 char e; if(S.top=S.base) /栈空 5 r

8、eturn 0; e=*(S.top-1); return e; int 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 1;

9、 int 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 1; int Pop1(SqStack1 &S,char &e) /删除运

10、算符栈栈顶元素，并用e返回 if(S.top=S.base)/栈空 return 0; -S.top; e=*S.top; return 1; 6 int Pop2(SqStack2 &S,int &e) /删除运算符栈栈顶元素，并用e返回 if(S.top=S.base) /栈空 return 0; -S.top; e=*S.top; return 1; char Precede(char d,char c)/判断d与c的优先级 switch(c) case+:switch(d) case+:return ;break; case-:return ;break; case*:return ;

11、break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case*:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; 7 case

12、:return ;break; case(:return ;break; case=:return ;break; case/:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; ca

13、se(:return ;break; case=:return ;break; case(:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; 8 case(:return

14、=;break; case):return ;break; case=:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case):return ;break; case=:return =;break; int Operate(int a,char theta,int b)/运算函数 switch(theta) case+:return (a+b); case-:return (a-b); case*:return

15、 (a*b); case/:return (a/b); case:return (pow(a,b); int EvaluateExpression/主要运算函数 char c,d,theta,x; int num,a,b; SqStack1 OPTR; SqStack2 OPND; InitStack1(OPTR);/构造运算符栈 InitStack2(OPND);/构造操作数栈 Push1(OPTR,=); c=getchar; while(c!=|GetTop1(OPTR)!=) num=0; if(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/不是运算符进

16、入操作数栈 while(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/将输入的操作数的字符型转换为整型 9 num*=10; num+=(c-48); c=getchar; Push2(OPND,num); else/是运算符 d=GetTop1(OPTR); switch(Precede(d,c)/运算符优先级比较 case:Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b);break; /运算，并将运算结果放入操作数栈 return GetTop2(OPND);/

17、返回操作数栈栈顶元素 主函数设计 void main int result; result=EvaluateExpression;/进行计算 printf(%dn,result);/输出结果 四、程序调试分析 开始进行编程时，只设计了一个栈的类型，无法将运算符和操作数分开存储，在老师讲解下，问题得以解决。同时将处理栈的函数,如Pop,Push等都针对运算对象进行了重新设置，一个处理运算符，一个处理操作数。 开始时未意识到输入的操作数为char型，应转换为int型，以后进行编程时应注意操作对象的类型。 五、程序运行结果 输入合法的表达式，以=结尾，在屏幕上输出表达式的值。 测试1： 14+6*3

18、/2= 23 测试2： 15-2/2+42= 10 30 六、程序清单 #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SqStack1 char * base; char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct SqStack2 int * base; int * top; int stacksize; SqStack2; /定义操作数栈数据类型 int InitStack1

19、(SqStack1 &S); int InitStack2(SqStack2 &S); int Push1(SqStack1 &S,char e); int Push2(SqStack2 &S,int e); char Precede(char d,char c); char GetTop1(SqStack1 &S); int GetTop2(SqStack2 &S); int Pop1(SqStack1 &S,char &e); int Pop2(SqStack2 &S,int &e); int Operate(int a,char theta,int b); int EvaluateExp

20、ression; void main int result; result=EvaluateExpression;/进行计算 printf(%dn,result);/输出结果 int EvaluateExpression/主要运算函数 char c,d,theta,x; 11 int num,a,b; SqStack1 OPTR; SqStack2 OPND; InitStack1(OPTR);/构造运算符栈 InitStack2(OPND);/构造操作数栈 Push1(OPTR,=); c=getchar; while(c!=|GetTop1(OPTR)!=) num=0; if(c!=+&

21、c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/不是运算符进入操作数栈 while(c!=+&c!=-&c!=*&c!=/&c!=&c!=(&c!=)&c!=)/将输入的操作数的字符型转换为整型 num*=10; num+=(c-48); c=getchar; Push2(OPND,num); else/是运算符 d=GetTop1(OPTR); switch(Precede(d,c)/运算符优先级比较 case:Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b);break; /

22、运算，并将运算结果放入操作数栈 return GetTop2(OPND);/返回操作数栈栈顶元素 int InitStack1(SqStack1 &S) /构造运算符栈 S.base=(char*)malloc(STACK_INIT_SIZE *sizeof(char);/申请存储空间 if(!S.base) exit(OVERFLOW);/存储空间分配失败 S.top=S.base; 12 S.stacksize=STACK_INIT_SIZE; return 1; int InitStack2(SqStack2 &S)/构造操作数栈 S.base=(int *)malloc(STACK_I

23、NIT_SIZE * sizeof(int); /申请存储空间 if(!S.base) exit(OVERFLOW); /存储空间分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; char GetTop1(SqStack1 &S)/取得运算符栈栈顶元素 char e; if(S.top=S.base)/栈空 return 0; e=*(S.top-1); return e; int GetTop2(SqStack2 &S) /取得操作数栈栈顶元素 char e; if(S.top=S.base) /栈空 return 0; e=

24、*(S.top-1); return e; int 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; 13 return 1; int Pus

25、h2(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 1; int Pop1(SqStack1 &S,char &e) /删除运算符栈栈顶元素，

26、并用e返回 if(S.top=S.base)/栈空 return 0; -S.top; e=*S.top; return 1; int Pop2(SqStack2 &S,int &e) /删除运算符栈栈顶元素，并用e返回 if(S.top=S.base) /栈空 return 0; -S.top; e=*S.top; return 1; char Precede(char d,char c)/判断d与c的优先级 switch(c) case+:switch(d) 14 case+:return ;break; case-:return ;break; case*:return ;break;

27、case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case*:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; case:return ;

28、break; case(:return ;break; case=:return ;break; case/:switch(d) case+:return ;break; case-:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case:switch(d) 15 case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case(:re

29、turn ;break; case=:return ;break; case(:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return ;break; case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case(:return =;break;

30、 case):return ;break; case=:switch(d) case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case:return ;break; case):return ;break; case=:return =;break; int Operate(int a,char theta,int b)/运算函数 16 switch(theta) case+:return (a+b); case-:return (a-b); case*:return (a*b); case/:return (a/b); case:return (pow(a,b); 17