数据结构课程设计：算术表达式.doc

《数据结构》课程设计
表达式求值
一 目的
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果

二 需求分析
设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。
1. 程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量 ）。为了简化，操作数只能为浮点数，操作符 为 “ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。

2. 程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变 化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。

3.功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）：
（1）是数字，则判断该数字的合法性。
（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表 达 式的值。
（3）若是其它字符，则返回错误信息。
若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

三 概要设计
1.数据结构的选择：
任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈 来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作 的线性表。
为了实现算符优先算法，可以使用两个工作栈。一个称做SqStack1，用以寄存运算符；另一个称做SqStack2，用以寄存操作数或运算结果。首先置操作数栈为空栈，表达式起始符“＃”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，若是操作数则进入SqStack2栈，若是运算符则和SqStack1栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕。
两个栈： typedef struct //运算符栈
{
char *base;
char *top;
int stacksize;
}SqStack1;

typedef struct //运算数栈
{
float *base;
float *top;
int stacksize;
}SqStack2;
2.相关功能函数：
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);//声明比较函数
通过这个函数我们来实现运算符运算的先后顺序判断运算符优先权，返回优先权高的
算符间的优先关系如下：
θ1 θ2
+
-
*
/
（
）
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
（
<
<
<
<
<
=

）
>
>
>
>

>
>
#
<
<
<
<
<

=
最后的计算函数：
float Operate(float a,char rheta,float b);//声明运算函数
为了使运算的过程更加直观的反应出来，我们再绘制一个表格，绘制表格的相关函数如下：
void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素
void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素
3.函数模块之间的调用关系：

四 详细设计

首先本程序定义两个顺序栈：运算符栈（SqStack1）和运算数栈（SqStack2）；
typedef struct //运算符栈
{
char *base;
char *top;
int stacksize;
}SqStack1;

typedef struct //运算数栈
{
float *base;
float *top;
int stacksize;
}SqStack2;

然后是主要功能函数的详细设计：
/*运算符栈函数*/
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;
}
}
}

核心的算法确定如何入栈函数的实现如下
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;
}

五 调试分析
1．结构分析:
栈中的数据节点是通过数组来存储的。因为在C语言中数组是用下标从零开始的，因此我们在调用他们的数据是要特别注意。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。如果输入的数字不符合题目要求，则会产生错误结果。
2．算法的时空分析：
时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。

六 测试结果
1、实数混合运算

以上调试结果是正确的。能够实现各个符号优先级先后顺序的运算，根据符号优先级（、）、+、-、*、/ ，如此顺序进行运算，实现了基本表达式运算的功能。
但是需要注意的是，这个程序功能并不是那么完善，具体能实现的功能如下：
由于中英文字符的不同，加上本程序没有对中文字符加以处理，当从键盘输入的表达式中包含中文括号时程序无法正确的计算出结果，而是会报错！同样表达式中只能包含英文的运算符，输入中文的运算符时会报错！
同样，从键盘输入的表达式必须要运算符匹配，例如括号要匹配，要成对出现，由于本程序没有加以处理，遇到这种情况，程序会报错！
七 用户使用说明
1． 使用环境：Visual C++ 6.0.
2． 操作要求：程序运行后,用户根据提示输入0—9之间的数字或者是字符以进入相应的功能处理函数。程序调用建表功能函数后，用户将按照规定的方式输入你所要计算的表达式，最后可以计算出结果。
3． 用户需要从键盘输入正确的表达式，表达式中不可出现中文符号，运算符要匹配。
4． 该程序支持整数，小数的运算，四则混合运算。
八 课程设计总结
数据结构的研究不仅涉及到计算机硬件的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。
在课程设计中，应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速的算法；如果待解决的问题数据量极大，机器的存储空间较小，则在编写算法时应该考虑如何节省空间。以后在编写程序时就应该注意到所编写程序的时间复杂度，以及是否运用了良好的算法，而不能只是像以前编写程序时单纯使用C语言的知识，要充分考虑程序的性能，争取编写出更优良的程序来。
经过两个星期的实际操作和搜索相关资料，终于让我完成了任务。让我对《数据结构》C语言有了更进一步的认识和了解，也让我知道，要想学好它要重在实践，理论与实际应用相结合，提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。通过实际操作，我也发现我的好多不足之处：
(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。
(2)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。
(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。
10
中南民族大学计算机科学学院 专业：软件工程 学号：201421092032 姓名 ：李凯