数据结构算术表达式求值实验.docx
《数据结构算术表达式求值实验.docx》由会员分享，可在线阅读，更多相关《数据结构算术表达式求值实验.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构算术表达式求值实验
北京理工大学珠海学院
《数据结构》课程设计报告
题目：
____________算术表达式求值_________________
所在学院：
专业班级：
学生姓名：
指导教师：
2010年05月26日
1．前言1
2．概要设计1
2.1数据结构设计1
2.2算法设计1
2.3ADT描述2
2.4功能模块分析2
3．详细设计3
3.1数据存储结构设计3
3.2主要算法流程图（或算法伪代码）3
4．软件测试6
5．心得体会8
参考文献8
附录8
1．前言
在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。
因而在程序设计时，借助栈实现。
算法输入：
一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。
为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。
算法输出：
表达式运算结果。
算法要点：
设置运算符栈和运算数栈辅助分析算符优先关系。
在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
2．概要设计
2.1数据结构设计
任何一个表达式都是由操作符，运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符。
栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。
2.2算法设计
为了实现算符优先算法。
可以使用两个工作栈。
一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。
2.3ADT描述
ADTStack{
数据对象：
D={
|
∈ElemSet,i=1,2,…，n,n≧0}
数据对象：
R1={<
>|
i=2,…，n}
约定
端为栈顶，
端为栈底。
基本操作：
InitStack（&S）
操作结果：
构造一个空栈S。
GetTop（S）
初始条件：
栈S已存在。
操作结果：
用P返回S的栈顶元素。
Push（&S，ch）
初始条件：
栈S已存在。
操作结果：
插入元素ch为新的栈顶元素。
Pop（&S）
初始条件：
栈S已存在。
操作结果：
删除S的栈顶元素。
In（ch）
操作结果：
判断字符是否是运算符，运算符即返回1。
Precede（c1,c2）
初始条件：
c1,c2为运算符。
操作结果：
判断运算符优先权，返回优先权高的。
Operate（a,op,b）
初始条件：
a,b为整数，op为运算符。
操作结果：
a与b进行运算，op为运算符，返回其值。
num（n）
操作结果：
返回操作数的长度。
EvalExpr（）
初始条件：
输入表达式合法。
操作结果：
返回表达式的最终结果。
}ADTStack
2.4功能模块分析
1.栈的基本功能。
InitStack（Stack*s）和InitStack2（Stack2*s）分别构造运算符栈与构造操作数栈，Push（Stack*s,charch）运算符栈插入ch为新的栈顶元素，Push2（Stack2*s,intch）操作数栈插入ch为新的栈顶元素，Pop（Stack*s）删除运算符栈s的栈顶元素，用p返回其值，Pop2（Stack2*s）删除操作数栈s的栈顶元素，用p返回其值，GetTop（Stacks）用p返回运算符栈s的栈顶元素，GetTop2（Stack2s）用p返回操作数栈s的栈顶元素。
2.其它功能分析。
（1）In（charch）判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='（'||ch=='）'||ch=='#'）。
（2）Precede（charc1,charc2）判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。
（3）Operate（inta,charop,intb）操作数用对应的运算符进行运算功能。
运算结果直接返回。
（4）num（intn）求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。
（5）EvalExpr（）主要操作函数运算功能。
分析详细见“3.详细设计…3.2”。
3．详细设计
3.1数据存储结构设计
因为表达式是由操作符，运算符和界限符组成的。
如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。
/*定义字符类型栈*/
typedefstruct{
intstacksize;
char*base;
char*top;
}Stack;
/*定义整型栈*/
typedefstruct{
intstacksize;
int*base;
int*top;
}Stack2;
3.2主要算法流程图（或算法伪代码）
1.Precede（charc1,charc2）判断运算符优先权，返回优先权高的。
算符间的优先关系如下：
+
-
*
/
（
）
#
+
>
<
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
（
<
<
<
<
<
=
）
>
>
>
>
>
>
#
<
<
<
<
<
=
表1
算法伪代码如下：
charPrecede（charc1,charc2）
{
staticchararray[49]={
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','!
',
'>','>','>','>','!
','>','>',
'<','<','<','<','<','!
','='};//用一维数组存储49种情况
switch（c1）
{
/*i为下面array的横标*/
case'+':
i=0;break;
case'-':
i=1;break;
case'*':
i=2;break;
case'/':
i=3;break;
case'（':
i=4;break;
case'）':
i=5;break;
case'#':
i=6;break;
}
switch（c2）
{
/*j为下面array的纵标*/
case'+':
j=0;break;
case'-':
j=1;break;
case'*':
j=2;break;
case'/':
j=3;break;
case'（':
j=4;break;
case'）':
j=5;break;
case'#':
j=6;break;
}
return（array[7*i+j]）;/*返回运算符array[7*i+j]为对应的c1,c2优先关系*/
}
2.intEvalExpr（）主要操作函数。
算法概要流程图：
利用该算法对算术表达式3*（7-2）求值操作过程如下：
步骤
OPTR栈
OPND栈
输入字符
主要操作
1
#
3*（7-2）#
Push（OPND,’3’）
2
#
3
*（7-2）#
Push（OPTR,’*’）
3
#*
3
（7-2）#
Push（OPNR,’（’）
4
#*（
3
7-2）#
Push（OPND,’7’）
5
#*（
37
-2）#
Push（OPNR,’-’）
6
#*（-
37
2）#
Push（OPND,’2’）
7
#*（-
372
）#
Operate（‘7’,’-’,’2’）
8
#*（
35
）#
Pop（OPTR）
9
#*
35
#
Operate（‘3’,’*’,5’）
10
#
15
#
Return（GetTop2（OPND））
表2
算法伪代码如下：
intEvalExpr（）//主要操作函数
{c=*ptr++;
while（c!
='#'||GetTop（OPTR）!
='#'）
{
if（!
In（c））//不是运算符即进栈
{if（!
In（*（ptr-1）））ptr=ptr-1;
m=atoi（ptr）;//取字符串前面的数字段
n=num（m）;
Push2（&OPND,m）;
ptr=ptr+n;
c=*ptr++;
}
else
switch（Precede（GetTop（OPTR）,c））
{
case'<':
//栈顶元素优先权底
Push（&OPTR,c）;
c=*ptr++;
break;
case'=':
//脱括号并接收下一字符
x=Pop（&OPTR）;
c=*ptr++;
break;
case'>':
//退栈并将运算结果入栈
theta=Pop（&OPTR）;
b=Pop2（&OPND）;a=Pop2（&OPND）;
Push2（&OPND,Operate（a,theta,b））;
break;
}
}
4．软件测试
1.运行成功后界面。
2.输入正确的表达式后。
3.更改表达式，输入有2位数的整数调试。
5．心得体会
这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。
课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。
就像我在写EvalExpr（）函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。
在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。
发现上机的重要作用，特别算术表达式有了深刻的理解。
这个程序是我们3个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。
某个人的离群都可能导致导致整项工作的失败。
实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。
团结协作是我们成功的一项非常重要的保证。
而这次课程设计也正好锻炼我们这一点，这也是非常宝贵的
最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。
参考文献：
1.《数据结构（C语言版）》严蔚敏清华大学出版社
2.《C语言程序设计》丁峻岭中国铁道出版社
3.《C程序设计》谭浩强清华大学出版社
附录
程序源代码：
#include
#include
#include
#defineNULL0
#defineOK1
#defineERROR-1
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT20
/*定义字符类型栈*/
typedefstruct{
intstacksize;
char*base;
char*top;
}Stack;
/*定义整型栈*/
typedefstruct{
intstacksize;
int*base;
int*top;
}Stack2;
/*-----------------全局变量---------------*/
StackOPTR;/*定义运算符栈*/
Stack2OPND;/*定义操作数栈*/
charexpr[255]="";/*存放表达式串*/
char*ptr=expr;
intInitStack（Stack*s）//构造运算符栈
{
s->base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
if（!
s->base）returnERROR;
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
returnOK;
}
intInitStack2（Stack2*s）//构造操作数栈
{
s->base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
if（!
s->base）returnERROR;
s->stacksize=STACK_INIT_SIZE;
s->top=s->base;
returnOK;
}
intIn（charch）//判断字符是否是运算符，运算符即返回1
{
return（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='（'||ch=='）'||ch=='#'）;
}
intPush（Stack*s,charch）//运算符栈插入ch为新的栈顶元素
{
*s->top=ch;
s->top++;
return0;
}
intPush2（Stack2*s,intch）//操作数栈插入ch为新的栈顶元素
{
*s->top=ch;
s->top++;
return0;
}
charPop（Stack*s）//删除运算符栈s的栈顶元素，用p返回其值
{
charp;
s->top--;
p=*s->top;
returnp;
}
intPop2（Stack2*s）//删除操作数栈s的栈顶元素，用p返回其值
{
intp;
s->top--;
p=*s->top;
returnp;
}
charGetTop（Stacks）//用p返回运算符栈s的栈顶元素
{
charp=*（s.top-1）;
returnp;
}
intGetTop2（Stack2s）//用p返回操作数栈s的栈顶元素
{
intp=*（s.top-1）;
returnp;
}
/*判断运算符优先权，返回优先权高的*/
charPrecede（charc1,charc2）
{
inti=0,j=0;
staticchararray[49]={
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=','!
',
'>','>','>','>','!
','>','>',
'<','<','<','<','<','!
','='};
switch（c1）
{
/*i为下面array的横标*/
case'+':
i=0;break;
case'-':
i=1;break;
case'*':
i=2;break;
case'/':
i=3;break;
case'（':
i=4;break;
case'）':
i=5;break;
case'#':
i=6;break;
}
switch（c2）
{
/*j为下面array的纵标*/
case'+':
j=0;break;
case'-':
j=1;break;
case'*':
j=2;break;
case'/':
j=3;break;
case'（':
j=4;break;
case'）':
j=5;break;
case'#':
j=6;break;
}
return（array[7*i+j]）;/*返回运算符*/
}
/*操作函数*/
intOperate（inta,charop,intb）
{
switch（op）
{
case'+':
return（a+b）;
case'-':
return（a-b）;
case'*':
return（a*b）;
case'/':
return（a/b）;
}
return0;
}
intnum（intn）//返回操作数的长度
{
charp[10];
itoa（n,p,10）;//把整型转换成字符串型
n=strlen（p）;
returnn;
}
intEvalExpr（）//主要操作函数
{
charc,theta,x;intn,m;
inta,b;
c=*ptr++;
while（c!
='#'||GetTop（OPTR）!
='#'）
{
if（!
In（c））
{if（!
In（*（ptr-1）））ptr=ptr-1;
m=atoi（ptr）;//取字符串前面的数字段
n=num（m）;
Push2（&OPND,m）;
ptr=ptr+n;
c=*ptr++;
}
else
switch（Precede（GetTop（OPTR）,c））
{
case'<':
Push（&OPTR,c）;
c=*ptr++;
break;
case'=':
x=Pop（&OPTR）;
c=*ptr++;
break;
case'>':
theta=Pop（&OPTR）;
b=Pop2（&OPND）;a=Pop2（&OPND）;
Push2（&OPND,Operate（a,theta,b））;
break;
}
}
returnGetTop2（OPND）;
}
intmain（）
{
printf（"请输入正确的表达式以'#'结尾:
"）;
do{
gets（expr）;
}while（!
*expr）;
InitStack（&OPTR）;/*初始化运算符栈*/
Push（&OPTR,'#'）;/*将#压入运算符栈*/
InitStack2（&OPND）;/*初始化操作数栈*/
printf（"表达式结果为:
%d\n",EvalExpr（））;
return0;
}
课程设计成绩评定表
教师评语
1、课程设计表现：
2、程序、软件质量：
3、设计报告质量：
4、答辩表现：
5、独到的见解、方法与创新性：
6、总结：
成绩记录
平时成绩（10分）
程序检查（20+20分）
设计报告文档（20分）
课程设计答辩（20+10分）
最后（百分）成绩
成绩（等级）评定
升级会员 