数据结构课程设计表达式求值实验报告.doc

数据结构课程设计表达式求值实验报告

22
2020年4月19日
文档仅供参考，不当之处，请联系改正。

实验课程名称
专 业 班 级
学 生 姓 名
学 号
指 导 教 师

20 至 20 年第 学期第 至 周

算术表示式求值演示
一、 概述
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是算术表示式求值演示。表示式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表示式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。

二、 系统分析

1． 以字符列的形式从终端输入语法正确的、不含变量的整数表示式。利用已知的算符优先关系，实现对算术四则混合运算表示式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表示式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，能够使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
3． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。
4． 程序执行时的命令：
本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表示式即可。（要注意输入时格式，否者可能会引起一些错误）
5. 测试数据。

三、 概要设计
一个算术表示式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，因此一个表示式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表示式的求值计算。
算法设计
程序包含三个模块
(1) 主程序模块，其中主函数为
void main{
输入表示式；
根据要求进行转换并求值；
输出结果；
}
(2) 表示式求值模块——实现具体求值。
(3) 表示式转换模块——实现转换。

各个函数之间的调用关系
主函数
表示式转换

表示式求值
数据输入
输出
输出

栈的抽象数据类型定义
ADT SqStack{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}
约定其中ai端为栈底，an端为栈顶。

操作集合：
(1)void InitStack1(SqStack1 &S1);//声明栈建立函数
(2)void InitStack2(SqStack2 &S2);//声明栈建立函数
(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数
(4)void Push1(SqStack1 &S1,char e);//声明入栈函数
(5)void Push2(SqStack2 &S2,float e);//声明入压栈函数
(6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数
(7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数
(8)char Pop1(SqStack1 &S1);//声明出栈函数
(9)float Pop2(SqStack2 &S2);//声明出栈函数
(10)char Compare(char m,char n);//声明比较函数
(11)float Operate(float a,char rheta,float b);//声明运算函数
(12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素
(13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素
}ADT SqStack
结构分析:
栈中的数据节点是经过数组来存储的。因为在C语言中数组是用下标从零开始的，因此我们在调用她们的数据是要特别注意。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能经过P来访问结点，否则会引起程序错误。如果输入的数字不符合题目要求，则会产生错误结果。
算法的时空分析：
时间和空间性能分析：时间上，对于含n个字符的表示式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表示式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表示式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。

四、 详细设计

源程序

#include<iostream>
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct //运算符栈
{
char *base;
char *top;
int stacksize;
}SqStack1;

typedef struct //运算数栈
{
float *base;
float *top;
int stacksize;
}SqStack2;
void InitStack1(SqStack1 &S1);//声明栈建立函数
void InitStack2(SqStack2 &S2);//声明栈建立函数
void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数
void Push1(SqStack1 &S1,char e);//声明入栈函数
void Push2(SqStack2 &S2,float e);//声明入压栈函数
char GetTop1(SqStack1 &S1);//声明取栈顶元素函数
float GetTop2(SqStack2 &S2);//声明取栈顶元素函数
char Pop1(SqStack1 &S1);//声明出栈函数
float Pop2(SqStack2 &S2);//声明出栈函数
char Compare(char m,char n);//声明比较函数
float Operate(float a,char rheta,float b);//声明运算函数
void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素
void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素

/*主函数*/

void main()
{

SqStack1 S1;//定义运算符栈
SqStack2 S2;//定义运算数栈

//freopen("data1.in","r",stdin);
//freopen("data1.out","w",stdout);

InitStack1(S1);//调用栈建立函数
InitStack2(S2);//调用栈建立函数
evaluate(S1,S2);//调用确定如何入栈函数
cout<<"按任意键结束!"<<endl;

}

/*运算符栈函数*/
void InitStack1(SqStack1 &S1)//构造一个空栈S1
{
S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char));
if(!S1.base)cout<<"存储分配失败！";//存储分配失败
S1.top=S1.base;
S1.stacksize=STACK_INIT_SIZE;
}
void Push1(SqStack1 &S1,char e)//入栈
{
if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间
{
S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));
if(!S1.base) cout<<"存储分配失败！";
else
{
S1.top=S1.base+S1.stacksize;
S1.stacksize=S1.stacksize+STACKINCREMENT;
}
}
*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移
}

char GetTop1(SqStack1 &S1)//取栈顶元素
{
char e;
if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";
else e=*(S1.top-1);
return e;
}

void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素
{
char e,*p;
if(S1.top==S1.base)cout<<" ";
else
{
p=S1.base;
while(p<S1.top)
{
e=*p;
p++;
cout<<e;
}
}
}
char Pop1(SqStack1 &S1)//出栈
{
char e;
if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";
e=*(--S1.top);
return e;
}
/*运算数栈函数*/
void InitStack2(SqStack2 &S2)//构造一个空栈S2
{
S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float));
if(!S2.base)cout<<"存储分配失败！";//存储分配失败
S2.top=S2.base;
S2.stacksize=STACK_INIT_SIZE;
}
void Push2(SqStack2 &S2,float e)//入栈
{
if(S2.top-S2.base>=S2.stacksize)//栈满，追加存储空间
{
S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));
if(!S2.base)cout<<"存储分配失败！";
else
{
S2.top=S2.base+S2.stacksize;
S2.stacksize=S2.stacksize+STACKINCREMENT;
}
}
*S2.top=e;S2.top=S2.top+1;//将元素e入栈，指针上移
}
void DispStack2(SqStack2 &S2)//从栈底到栈顶依次输出各元素
{
float e,*p;
if(S2.top==S2.base)cout<<" ";
else
{
p=S2.base;
while(p<S2.top)
{
e=*p;
p++;
cout<<e;
}
}
}
float GetTop2(SqStack2 &S2)//取栈顶元素
{
float e;
if(S2.top==S2.base) cout<<"\n\t\t运算数栈已空!";
else e=*(S2.top-1);
return e;
}
float Pop2(SqStack2 &S2)//出栈
{
float e;
if(S2.top==S2.base)cout<<"\n\t\t运算数栈已空!";
e=*(--S2.top);
return e;
}
/*确定如何入栈函数*/
void evaluate(SqStack1 &S1,SqStack2 &S2)
{
char c;
float t,e;
int n=0,i=1,j=0,k=0,l=0;
char ch[STACK_INIT_SIZE];
int s=1;
int flag=0,flag2=0;
float p1,p2;
char ch1;
Push1(S1,'#');//将'#'入栈，作为低级运算符
cout<<"●请输入不含变量的表示式（以#结束!）：\n ";
cin>>ch;
c=ch[0];
cout<<"\n●对表示式求值的操作过程如下："
<<"\n________________________________________________________________________________\n"
<<"步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作";
while(c!='#'||GetTop1(S1)!='#')
{
cout<<"\n________________________________________________________________________________\n";
cout<<i++<<"\t";
DispStack1(S1);cout<<"\t\t";
DispStack2(S2);
cout<<"\t\t";
if(flag==1)
{
k--;
flag=0;
}
if(flag2)
{
k+=flag2;
flag2=0;
}
for(l=0;l<k;l++)
cout<<' ';
for(j=k;ch[j]!='\0';j++)
cout<<ch[j];
if(ch[k]!='#'&&flag!=1) {k++;flag=0;}
as:
if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#'))
{//输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数
if(!(c=='.')&&n>=0)
{
e=float(c-48);
n++;
if(n==1)t=e;
else if(n>1)t=t*10+e;
c=ch[s++];
}
if(n==-1)
{
e=float(c-48);
t=t+e/10;
c=ch[s++];
}
if(c=='.')
{
n=-1;
c=ch[s++];
}
if((c>='0'&&c<='9')||c=='.')
{
flag2++;
goto as;
}

if(c<'0'||c>'9')

{
Push2(S2,t);
}

cout<<"\t\tPush2(S2,"<<t<<")";
}
else//输入的是运算符
{
n=0;//非运算型数据计数器清零

switch(Compare(GetTop1(S1),c))//比较运算符的优先级
{
case '<'://栈顶元素优先级低，则入栈且继续输入
Push1(S1,c);
cout<<"\t\tPush1(S1,"<<c<<")";
c=ch[s++];
break;
case '='://栈顶元素优先级相等，脱括号并接收下一字符
Pop1(S1);
cout<<"\t\tPop1(S1)";
c=ch[s++];
break;
case '>'://栈顶元素优先级高，则退栈并将运算结果入栈
p1=Pop2(S2);
p2=Pop2(S2);
ch1=Pop1(S1);
Push2(S2,Operate(p2,ch1,p1));
cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';
flag=1;
break;
}

}
}
cout<<"\n________________________________________________________________________________\n";
cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";
for(j=0;j<k;j++) cout<<' ';
cout<<"#"<<"\t\t"<<"RETURN(GETTOP(S2))";
cout<<"\n________________________________________________________________________________\n";

if(S2.top-1==S2.base)//显示表示式最终结果
cout<<"\n●表示式的结果为："<<GetTop2(S2)<<endl;
else cout<<"\n表示式出错!\n";
}

char Compare(char m,char n)//运算符的优先级比较
{
if(n=='+'||n=='-')//输入符号为"+"、"-"
{
if(m=='('||m=='#')return '<';//栈顶元素为"("、"#",此时栈顶符号优先级低，返回"<"
else return '>';//否则，栈顶符号优先级高,返回">"
}
else if(n=='*'||n=='/')//输入的符号为"*"、"/"
{
if(m==')'||m=='*'||m=='/')return '>';//栈顶元素为")"、"*"、"/",此时栈顶符号优先级高，返回">"
else return '<';//否则，栈顶符号优先级低,返回"<"
}
else if(n=='(')return'<';//输入的符号为"(",则直接返回"<"
else if(n==')')//输入的符号为")"
{
if(m=='(')return'=';//栈顶元素为"(",此时优先级同，返回"="
else return '>';//否则，栈顶符号优先级高,返回">"
}
else //输入符号为其它
{
if(m=='#')return'=';//栈顶元素为"#",此时优先级同，返回"="
else return '>';//否则，栈顶符号优先级高,返回">"
}
}
float Operate(float a,char theta,float b)//运算函数
{
float tmp=0;
if (theta=='+')tmp=a+b;//从运算符栈取出的符号为"+"，则运算数栈的两元素相加，并返回
else if(theta=='-')tmp=a-b;//从运算符栈取出的符号为"-"，则运算数栈的两元素相减，并返回
else if(theta=='*')tmp=a*b;//从运算符栈取出的符号为"*"，则运算数栈的两元素相乘，并返回
else if(theta=='/') //从运算符栈取出的符号为"/"，则运算数栈的两元素相除，并返回
{
if(b==0) cout<<"\n表示式出错!除数不能为0!\n";
else tmp=a/b;
}
return tmp;
}
五、运行与测试

第六章 总结与心得

数据结构的研究不但涉及到计算机硬件的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。
在课程设计中，应该力求算法简明易懂，而易于转换为上机程序；如果程序重复多次使用，则应该尽可能选用快速的算法；如果待解决的问题数据量极大，机器的存储空间较小，则在编写算法时应该考虑如何节省空间。以后在编写程序时就应该注意到所编写程序的时间复杂度，以及是否运用了良好的算法，而不能只是像以前编写程序时单纯使用C语言的知识，要充分考虑程序的性能，争取编写出更优良的程序来。
让我对数据结构有了更进一步的认识和了解，也让我知道，要想学好它要重在实践，理论与实际应用相结合，提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能力。经过实际操作，我也发现我的好多不足之处：
(1)用栈的结构来解决表示式的求值，首先要解决的问题是如何将人们习惯书写的表示式转换成计算机容易处理的表示式。开始有些茫然，后来经过结合课本和同学的帮助完成了该课题。
(2)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。
(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。