数据结构实验.docx
数据结构实验数据结构与算法统计 专业：班级：学号：姓名： 实验报告 一、 实验目的 1. 学习使用C+实现栈的存储结构；.通过编程、上机调试，进一步理解栈的基本概念； 2. 锻炼独立编程与思考的能力，提升实践能力。 二、 实验内容 简单计算器。 请按照四则运算加、减、乘、除、幂和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。 例如，输入：4+2*5= 输出：14 输出：-48 输入：(4+2)*(2-10)= 三、 程序设计 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) 初始条件：栈S已存在且非空 操作结果：删除寄存运算符栈S的栈顶元素 Pop2(SqStack2 &S,int &e) 初始条件：栈S已存在且非空 操作结果：删除寄存操作数栈S的栈顶元素 Operate(int a,char theta,int b) 初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 Yunsuan 初始条件：输入合法的表达式 操作结果：返回表达式的值 ADT Stack 主程序流程 调用Yunsuan函数计算表达式的值，输出，在屏幕上打印出来。 各模块的调用关系 先由主函数调用计算求值模块；再由求值模块调用栈构造模块，表达式转换模块及表达式求值模块，计算并返回表达式的值；最后由主函数在屏幕上输出表达式的结果。 流程图 Y c进入操作数栈 返回运算结果 输出运算结果 c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!=''&&c!='('&&c!=')'&&cc!='='|GetTop1(OPTR)!='=' 开始 = 作为运算符栈的栈底字符 输入c case<:操作符入栈 case=:符号栈 case>:操作数入栈顶2个数运算 Y N 结束 2、详细设计 数据类型设计 typedef struct char * base; char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct 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) /栈空 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); *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); *S.top+=e; if(!S.base)exit(OVERFLOW);/分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; if(!S.base)exit(OVERFLOW); /分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; return 0; 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) 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) 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)/运算函数 switch(theta) case'+':return (a+b); int Yunsuan/主要运算函数 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!='=')/不是运算符进入case'-':return (a-b); case'*':return (a*b); case'/':return (a/b); case'':return (pow(a,b); 操作数栈 while(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!=''&&c!='('&&c!=')'&&c!='=')/将输入的操作数的字符型转换为整型 Push2(OPND,num); num*=10; num+=(c-48); c=getchar; 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 p; p=Yunsuan ;/进行计算 printf("%dn",p);/输出结果 四、 程序调试分析 1. 刚开始时没有思路，后来回顾了一下课上学习的内容，有所启发，认识到解决该问题需要设计两个栈； 2. 自己在编写时，容易输错字符，有时候不易发现，很麻烦，仔细程度还有待提高，还需要多进行编程练习； 五、 用户使用说明 运行程序，输入运算表达式，以“=”结束，然后敲击回车键，即可输出表达式的运算结果。 六、程序运行结果 1、输入：4+2*5= 输出：14 2、输入：(4+2)*(2-10)= 输出：-48 3、输入：(4/3-2)*(2-6)= 输出：4 七、程序清单 #include <iostream> #include <stdio.h> #include<stdlib.h> #include <math.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20 typedef struct char * base; char * top; int stacksize; SqStack1;/定义运算符栈数据类型 typedef struct 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 Yunsuan; int Yunsuan/设计主要运算函数 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!='=') /将输入的操作数的字符型转换为整型 num*=10; num+=(c-48); c=getchar; Push2(OPND,num); else/若是运算符 d=GetTop1(OPTR); 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; 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) /取得操作数栈栈顶元素 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;/运算，并将运算结果放入操作数栈 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; 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) 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) 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; return 0; 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); return 0; void main int p; p=Yunsuan;/进行计算 printf("%dn",p);/输出结果
