表达式求值实验报告 本文关键词：表达式，实验，报告，求值
表达式求值实验报告 本文简介：淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：表达式求值姓名：学号：专业班级：系（院）：计算机工程学院设计时间：设计地点：软件工程实验室、教室成绩：指导教师评语：签名：*年*月*日数据结构课程设计报告第22页，共21页1．课程设计目的1、训练学生灵活应用所学数据结构知识，独
表达式求值实验报告 本文内容：
淮
海
工
学
院
计算机工程学院
课程设计报告
设计名称：
数据结构课程设计
选题名称：
表达式求值
姓
名：
学
号：
专业班级：
系
（院）：
计算机工程学院
设计时间：
设计地点：
软件工程实验室、教室
成绩：
指导教师评语：
签名：*年*月*日
数据结构课程设计报告
第
22
页，共
21
页
1．课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
2．课程设计任务与要求：
任务
根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。
设计题目从任务书所列选题表中选取，每班每题不得超过2人。
学生自选课题
学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。
要求：
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。
2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;
4、每位同学需提交可独立运行的程序；
5
、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。
3．课程设计说明书
一
需求分析
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
[基本要求]
（1）
从键盘读入一个合法的算术表达式，输出正确的结果。
（2）
显示输入序列和栈的变化过程。
二
概要设计
1、设定“操作数”的栈的抽象数据类型定义：
ADT
SqStack_f{
数据对象：D={
数据关系：R1={|,,i=2,…，n}
约定端为栈顶，端为栈底。
基本操作：
InitStack_f(
//存储实型数据元素的一位数组
floattop;
//栈顶指针
int
stacksize;
//栈数组容量
}SqStack_f;
//有序存储实型的顺序表类型
typedef
struct{
charbase;
//存储字符数据元素的一位数组
chartop;
//栈顶指针
int
stacksize;
//栈数组容量
}SqStack_c;
//有序存储字符型的顺序表类型
void
InitStack_f(SqStack_fs)
void
InitStack_f(SqStack_fs)
//构造一个存储实型（字符型）的空栈，预设空间为100，分配失败就退出
void
GetTop_f(SqStack_fs,floate)
void
GetTop_c(SqStack_cs,chare)
//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序
void
Push_f(SqStack_fs,float
e)
void
Push_c(SqStack_cs,char
e)
//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
void
Pop_f(SqStack_fs,floate)
void
Pop_c(SqStack_cs,chare)
//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
其中部分操作的伪码算法（由于比较类似，以浮点型的栈为例）
void
InitStack_f(SqStack_fs)
{//构造一个存储实型的空栈，预设空间为100，分配失败就退出
s->base=(float)malloc(TTACK_INIT_SIZE*sizeof(float));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void
GetTop_f(SqStack_fs,floate)
{//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序
if(s->top==s->base)
{
printf(“ERROR!/n“);
exit(1);
}e=*(s->top-1);
}
void
Push_f(SqStack_fs,float
e)
{//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
if(s->top-s->base>=s->stacksize)
{
s->base=(float)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!s->base)
{
printf(“OVERFLOW!/n“);
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}s->top++=e;
}
void
Pop_f(SqStack_fs,floate)
{//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
if(s->top==s->base)
exit(1);e=*--s->top;
}
3、判断运算符优先级的算法：
算符间的优先关系如下：
+
-
/
(
)
#
+
>=
>
-
>
>=
>
>
>
>=
>
>
/
>
>
>
>=
>
(
>
>
>
>
>
#
=pre[1])
//栈顶元素优先级高返回1
return
1;
else
return
0;
//否则返回0
}
4、中缀表达式转换为后缀表达式的算法：
算法过程描述：
1)
首先将左括号“(”压进栈，作为栈底元素；
2)
从左而右对算数表达式进行扫描，每次读入一个字符s1[i]；
3)
若遇到数字或小数点，则立即写入s2[i]，若遇算数运算符，将“”（空格）写入s2[i]；
4)
遇到左括号“(”则压栈；
5)
若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到s2[i]，直到新栈顶元素的优先级比它低，然后将它压栈；
6)
若遇到右括号“）”，则将栈顶元素输出到s2[i]，直到栈顶元素为“（”，然后相互抵消；
7)
当扫描到“#”符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2[i]，并删除栈顶元素。
伪码算法：
void
Translate(chars1)
{
//中缀表达式转换为后缀表达式
char
s2[80];
SqStack_c
Optr;
int
i=0,j=0;
char
t;
InitStack_c(//初始化一个存储字符型的空栈，便于存储运算符
Push_c(//
首先将左括号“(”压进栈，作为栈底元素
while(s1[i]!=
#
)
//当扫描到的不是“#”，即表达式串没结束时
{
if(s1[i]>=
0
}
else
switch(s1[i])
//扫描到的是运算符
{
case
(
:Push_c(break;//
遇到左括号“(”则压栈
case
)
:Pop_c(
//若遇到右括号“）”，则将栈顶元素输出到s2[i]
while(t!=
(
)
//直到栈顶元素为“（”，然后相互抵消
{
s2[j++]=t;
Pop_c(
}
break;
default:while(GetTop_c(//栈顶元素优先级高，则弹出到s2[i]
s2[j++]=t;
}
Push_c(//栈顶元素优先级低，直接压栈
}
i++;
}
Pop_c(
while(t!=
(
)
//表达式串已结束，栈中的运算符全部输出到s2[i]，并删除栈顶元素
{
s2[j++]=t;
Pop_c(
}
for(i=0;i=
0
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,printf(“The
result
is:%g/n“,m);
}
else
//读入的为运算符
{
Pop_f(s,//弹出栈顶元素
Pop_f(s,//弹出次顶元素
switch(s2[i])
{//让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈
case
+
:z=y+x;printf(“The
result
is:%g/n“,z);break;
case
-
:z=y-x;printf(“The
result
is:%g/n“,z);break;
case
:z=y*x;printf(“The
result
is:%g/n“,z);break;
case
/
:if(x==0)
{//报错功能
printf(“表达式出错，除数为‘0’，无意义/n“);
exit(1);
}
else
{
z=y/x;
printf(“The
result
is:%g/n“,z);break;
}
case
^
:z=1;for(j=1;j
#include
#include
#define
TTACK_INIT_SIZE
100
//初始分配最大空间量
#define
STACKINCREMENT
10
//（默认）增补空间量
typedef
struct{
floatbase;
//存储实型数据元素的一维数组
floattop;
//栈顶指针
int
stacksize;
//栈数组容量
}SqStack_f;
//有序存储实型的顺序表类型
typedef
struct{
charbase;
//存储字符数据元素的一维数组
chartop;
//栈顶指针
int
stacksize;
//栈数组容量
}SqStack_c;
//有序存储字符型的顺序表类型
void
InitStack_f(SqStack_fs)
{//构造一个存储实型的空栈，预设空间为100，分配失败就退出
s->base=(float)malloc(TTACK_INIT_SIZE*sizeof(float));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void
InitStack_c(SqStack_cs)
{//构造一个存储字符型的空栈,预设空间为100,分配失败就退出
s->base=(char)malloc(TTACK_INIT_SIZE*sizeof(char));
if(!s->base)
exit(1);
s->top=s->base;
s->stacksize=TTACK_INIT_SIZE;
}
void
GetTop_f(SqStack_fs,floate)
{//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR“,并退出程序
if(s->top==s->base)
{
printf(“ERROR!/n“);
exit(1);
}e=*(s->top-1);
}
void
GetTop_c(SqStack_cs,chare)
{//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
if(s->top==s->base)
{
printf(“ERROR!/n“);
exit(1);
}e=*(s->top-1);
}
void
Push_f(SqStack_fs,float
e)
{//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
if(s->top-s->base>=s->stacksize)
{
s->base=(float)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!s->base)
{
printf(“OVERFLOW!/n“);
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}s->top++=e;
}
void
Push_c(SqStack_cs,char
e)
{//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间
if(s->top-s->base>=s->stacksize)
{
s->base=(char)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));
if(!s->base)
{
printf(“栈满，溢出/n“);
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}s->top++=e;
}
void
Pop_f(SqStack_fs,floate)
{//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
if(s->top==s->base)
exit(1);e=*--s->top;
}
void
Pop_c(SqStack_cs,chare)
{//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序
if(s->top==s->base)
exit(1);e=*--s->top;
}
int
precede(char
Top_char,char
s1_char)
{//栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。判断它们的优先级
//若栈顶运算符优先级高，则返回1，否则返回0
int
i,pre[2];
char
op[2];
op[0]=Top_char;
//栈顶的运算符赋给op[0]
op[1]=s1_char;
//新读入的运算符赋给op[1]
for(i=0;i=pre[1])
//栈顶元素优先级高返回1
return
1;
else
return
0;
//否则返回0
}
void
Translate(chars1)
{
//中缀表达式转换为后缀表达式
char
s2[80];
SqStack_c
Optr;
int
i=0,j=0;
char
t;
InitStack_c(//初始化一个存储字符型的空栈，便于存储运算符
Push_c(//
首先将左括号“(“压进栈，作为栈底元素
while(s1[i]!=
#
)
//当扫描到的不是“#“，即表达式串没结束时
{
if(s1[i]>=
0
}
else
switch(s1[i])
//扫描到的是运算符
{
case
(
:Push_c(break;//
遇到左括号“(“则压栈
case
)
:Pop_c(
//若遇到右括号“）“，则将栈顶元素输出到s2[i]
while(t!=
(
)
//直到栈顶元素为“(“，然后相互抵消
{
s2[j++]=t;
Pop_c(
}
break;
default:while(GetTop_c(//栈顶元素优先级高，则弹出到s2[i]
s2[j++]=t;
}
Push_c(//栈顶元素优先级低，直接压栈
}
i++;
}
Pop_c(
while(t!=
(
)
//表达式串已结束，栈中的运算符全部输出到s2[i]，并删除栈顶元素
{
s2[j++]=t;
Pop_c(
}
for(i=0;i=
0
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,printf(“The
result
is:%g/n“,m);
}
else
//读入的为运算符
{
Pop_f(s,//弹出栈顶元素
Pop_f(s,//弹出次顶元素
switch(s2[i])
{//让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈
case
+
:z=y+x;printf(“The
result
is:%g/n“,z);break;
case
-
:z=y-x;printf(“The
result
is:%g/n“,z);break;
case
:z=y*x;printf(“The
result
is:%g/n“,z);break;
case
/
:if(x==0)
{//报错功能
printf(“表达式出错，除数为
0
，无意义/n“);
exit(1);
}
else
{
z=y/x;
printf(“The
result
is:%g/n“,z);break;
}
case
^
:z=1;for(j=1;j<=x;j++)
{//乘方的运算
z=z*y;
printf(“The
result
is:%g/n“,z);
}
}
Push_f(s,z);
i++;
}
}
}
void
result(SqStack_fs)
{
float
v;
GetTop_f(s,printf(“The
final
result
is:%g/n“,v);//以合适的形式输出结果，省去不必要的小数点
}
void
main()
{
SqStack_f
stack;
char
str[80],c=
Y
;
while(c==
y
||
c==
Y
)//判断是否继续本程序
{
printf(“|----------------------------------------------|/n“);
printf(“|
表达式求值
|/n“);
printf(“|-------本程序支持实数的加减乘除乘方运算-------|/n“);
printf(“|
请输入算术表达式，以
#
结束
|/n“);
printf(“|----------------------------------------------|/n“);
gets(str);//输入表达式
InitStack_f(//初始化一个存储运算结果（实型）的栈
Translate(str);//调用“中缀表达式转换为后缀表达式函数“printf(“转化后的后缀表达式为：/n“);//检验后缀表达式是否转换正确
puts(str);//输出后缀表达式
Calculate(//计算无括号表达式的值
result(//调用“结果输出函数“printf(“你想继续吗？
Y
或
y
为继续，其余为退出程序/n“);//增加程序的连续输入功能
c=getchar();
getchar();//吞噬掉输入判断符后的
/n
}
}
4.课程设计心得
在起初分析老师给的题目时，我只有一个大概的轮廓，包括算术表达式的运算规则，算术表达式所用到的数据结构，即栈，知道并会使用栈的基本运算，了解算术表达式求值的基本算法思想，操作数栈和算符栈的结合使用。
于是开始着手编写程序，将上述已经明白的知识点通过程序展现出来，包括两种栈的定义，涉及到的栈的功能函数的设计，以及基本的算术表达式的简单计算，才发现，虽然上述基本工作已经完成，但对于具体处理算术表达式时，出现了很多的语法问题，逻辑问题，包括：怎样区分算术表达式中的算符和操作数的问题，怎样进行优先级的判断和比较问题，怎样处理非法算符的问题；怎样处理非法操作数的问题，怎样处理括号匹配的问题，怎样处理操作数为多位数的问题，怎样处理当操作数从正整数范围扩充到实数范围时的问题，怎样处理具体调用功能函数时出现的问题，等等；这些问题困扰了我一部分时间，之后，经反复思考，反复查阅资料，反复浏览网络，同时与同学交流讨论，上述问题均得到了解决。
在解决算法设计过程中出现的难题之后，程序初步完成，但并不是到此为止，如何改进算法，如何提高算法的时间复杂度、空间复杂度，如何处理一些意想不到的错误和特有情况，也花了一部份时间。
在进行课程设计过程中，我发现，独立思考起到了很关键的作用，在遇到问题时，首先想到的并不是去请教老师，而是回忆所学的知识点、查阅书本和参考资料，网络也起到了一定的辅助作用；在必要时，与同学交流、讨论，交换思想和方法，同时巩固了知识点；与此同时，请教老师，指导程序的设计思想和方法。
谈谈不足之处，在本次课程设计中，在遇到问题和错误时，我有时显得很浮躁，有些急于求成。我感觉自己独立思考的能力和分析问题、解决问题的能力还有待于提高，知识点的巩固还需要进一步加强