北京理工大学数据结构实验报告2

《数据结构与算法统计》

实验报告

学院：

班级：

学号：

姓名：

一、实验目的

⑴熟悉VC++6.0环境，学习使用C++实现栈的存储结构；

⑵通过编程、上机调试，进一步理解栈的基本概念；

⑶锻炼动手编程，独立思考的能力。

二、实验内容

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

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

②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取

整进行计算。

例如，输入：4+2*5= 输出：14

输入：(4+2)*(2-10)= 输出：-48

三、程序设计

1、概要设计

为实现上述功能，应使用两个栈，分别寄存操作数和运算符。为此需要栈的抽象数据结构。

⑴栈的抽象数据类型定义如下：

ADT Stack{

数据对象：

D = { ai | ai ∈ElemSet, i=1,…,n，n≥0 }

数据关系：

R1 = { | 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运算的结果

EvaluateExpression()

初始条件：输入合法的表达式

操作结果：返回表达式的值

}ADT Stack

⑵主程序流程

调用EvaluateExpression()函数计算表达式的值，输出在屏幕上。

⑶各模块的调用关系

先由主函数调用计算求值模块；

再由求值模块调用栈构造模块，表达式转换模块及表达式求值模块，计算并返回表达式的值；

最后由主函数在屏幕上输出表达式的结果。

⑷流程图

2、详细设计 ⑴数据类型设计

typedef struct SqStack1 {

char * base;

开始

= 作为运算符栈的栈底字符

c!='='||GetTop1(OPTR)!='='

c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='^'&&c!='('&&c!=')'&&c!='='

case ’<’:操作符入栈 case ’=’:符号出栈 case ’>’:操作数栈栈顶2个数运算

输入c

结束

c 进入操作数栈

返回运算结果

输出运算结果

N

Y

Y

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) //栈空

{

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'/':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'=':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!='=')//将输入的操作数的字符型转换为整型

{

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("%d\n",result);//输出结果

}

四、程序调试分析

⑴开始进行编程时，只设计了一个栈的类型，无法将运算符和操作数分开存储，在老师讲解下，问题得以解决。同时将处理栈的函数,如Pop,Push等都针对运算对象进行了重新设置，一个处理运算符，一个处理操作数。

⑵开始时未意识到输入的操作数为char型，应转换为int型，以后进行编程时应注意操作对象的类型。

五、程序运行结果

输入合法的表达式，以=<回车>结尾，在屏幕上输出表达式的值。

测试1：

14+6*3/2=

23

测试2：

15-2/2+4^2=

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(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("%d\n",result);//输出结果

}

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!='=')//将输入的操作数的字符型转换为整型

{

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;

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;

}

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;

}

}

}

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)); }

}