北京理工大学数据结构实验报(2).docx
北京理工大学数据结构实验报数据结构与算法统计 实验报告 学院： 班级： 学号： 姓名： 1 一、实验目的 熟悉VC+6.0环境，学习使用C+实现栈的存储结构； 通过编程、上机调试，进一步理解栈的基本概念； 锻炼动手编程，独立思考的能力。 二、实验内容 实现简单计算器的功能,请按照四则运算加、减、乘、除、幂和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、和=： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志； 输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 1、概要设计 为实现上述功能，应使用两个栈，分别寄存操作数和运算符。为此需要栈的抽象数据结构。 栈的抽象数据类型定义如下： ADT Stack 数据对象： D = ai | ai ÎElemSet, i=1,n，n0 数据关系： R1 = <ai-1, ai> | ai-1,ai ÎD, i=2, ,n 基本操作： InitStack1(SqStack1 &S) 操作结果：创建一个空栈S，以存储运算符 InitStack2(SqStack2 &S) 操作结果：创建一个空栈S，以存储操作数 Push1(SqStack1 &S,char e) 初始条件：栈S已存在 操作结果：插入运算符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已存在且非空 操作结果：删除寄存运算符栈S的栈顶元素 Pop2(SqStack2 &S,int &e) 初始条件：栈S已存在且非空 操作结果：删除寄存操作数栈S的栈顶元素 Operate(int a,char theta,int b) 初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 EvaluateExpression 初始条件：输入合法的表达式 操作结果：返回表达式的值 ADT Stack 主程序流程 调用EvaluateExpression函数计算表达式的值，输出在屏幕上。 各模块的调用关系 先由主函数调用计算求值模块； 再由求值模块调用栈构造模块，表达式转换模块及表达式求值模块，计算并返回表达式的值； 最后由主函数在屏幕上输出表达式的结果。 流程图 3 开始 = 作为运算符栈的栈底字符 输入c c!='='|GetTop1(OPTR)!='=' Y c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!=''&&c!='('&&c!=')'&&c!='=' N case<:操作符入栈 case=:符号出栈 case>:操作数栈栈顶2个数运算 Y c进入操作数栈 返回运算结果 输出运算结果 结束 2、详细设计 数据类型设计 typedef struct SqStack1 char * base; 4 char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct SqStack2 int * 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 *)malloc(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 return 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; 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) /删除运算符栈栈顶元素，并用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 '>'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; 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; 7 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; 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; 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; case'':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; 8 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'=':return '='break; int Operate(int a,char theta,int b)/运算函数 switch(theta) case'+':return (a+b); case'-':return (a-b); case'*':return (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!='=')/不是运算符进入操作数栈 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'<':Push1(OPTR,c);c=getchar;break; /栈顶运算符优先级低，新输入的运算符进栈 case'=':Pop1(OPTR,x);c=getchar;break; /去括号 case'>':Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b);break; /运算，并将运算结果放入操作数栈 return GetTop2(OPND);/返回操作数栈栈顶元素 主函数设计 void main int result; result=EvaluateExpression;/进行计算 printf("%dn",result);/输出结果 四、程序调试分析 开始进行编程时，只设计了一个栈的类型，无法将运算符和操作数分开存储，在老师讲解下，问题得以解决。同时将处理栈的函数,如Pop,Push等都针对运算对象进行了重新设置，一个处理运算符，一个处理操作数。 开始时未意识到输入的操作数为char型，应转换为int型，以后进行编程时应注意操作对象的类型。 五、程序运行结果 输入合法的表达式，以=<回车>结尾，在屏幕上输出表达式的值。 测试1： 14+6*3/2= 23 测试2： 15-2/2+42= 10 30 六、程序清单 #include <iostream> #include <stdio.h> #include <math.h> #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(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 EvaluateExpression; 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!='+'&&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'<':Push1(OPTR,c);c=getchar;break; /栈顶运算符优先级低，新输入的运算符进栈 case'=':Pop1(OPTR,x);c=getchar;break; /去括号 case'>':Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b);break; /运算，并将运算结果放入操作数栈 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_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) /栈空 return 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; 13 return 1; 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) /删除运算符栈栈顶元素，并用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; 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; 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; 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; 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'':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; case'':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')':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
