算法表达式语法检查数据结构课程设计.docx
- 文档编号:14152722
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:59
- 大小:208.12KB
算法表达式语法检查数据结构课程设计.docx
《算法表达式语法检查数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《算法表达式语法检查数据结构课程设计.docx(59页珍藏版)》请在冰点文库上搜索。
算法表达式语法检查数据结构课程设计
《数据结构》课程设计
中南民族大学
计算机科学学院
课程设计报告
课
程
数据结构
题
目
算法表达式语法检查
年
级
2014
专
业
软件工程
学
生
柳真
学
号
201421092073
指导教师
刘赛
2015年12月20日
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真1
《数据结构》课程设计
中南民族大学计算机科学学院本科课程设计
任务书
设计名称:
算术表达式语法检查
指导教师:
下达时间:
2015-11-30
学生姓名:
学号:
年级专业:
2014级软件工程
一、课程设计的基本要求
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,
利用C/C++语言进行程序设计,并规范地完成课程设计报告。
通过课程设计,巩
固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理
解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计
建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基
本能力。
具体要求如下:
1、对现实复杂问题中的数据对象特性及组织方法进行分析和研究,设计
适当的数据逻辑结构、存贮结构以及相应运算操作,把现实世界问题建模转化为
计算机内部表示并进行处理。
2、采取模块化方式进行程序设计,要求程序的功能设计、数据结构设计
及整体结构设计合理。
学生也可根据自己对题目的理解增加新的功能模块(视情
况可另外加分)。
3、系统以菜单界面方式(至少采用文本菜单界面,如能采用图形菜单界
面更好)工作,运行界面友好,演示程序以用户和计算机的对话方式进行,利用
文件进行数据的提取与存储。
4、程序算法说明清晰,理论分析与计算正确,运行情况良好,实验测试
数据无误,容错性强(能对错误输入进行判断控制)。
5、编程风格良好(包括缩进、空行、适当注释、变量名和函数名见名知
意,程序容易阅读等);
6、写出规范的课程设计报告,具体要求见相关说明文档。
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真2
《数据结构》课程设计
二、课程设计的主要内容
题目描述:
算术表达式语法检查。
功能要求及说明:
(1)键盘读入一个四则运算算术表达式,对其进行语法检查;
(2)算术表达式允许嵌套,如果出错,指出出错位置;
(3)不需要计算结果;
(4)尽量不使用栈。
三、课程设计的进程安排
1.2015年11月30日:
布置并下达课程设计题目。
2.2015年12月7日之前:
联系指导教师,理解课程设计题目及相关要
求,查阅相关资料,进行课程设计(地点:
9-204,9-206)。
3.2015年12月7日至12月31日(第15周-第18周):
课程设计源程序
的调试、修改与检查,书写课程设计报告(地点:
计算机科学学院实验
机房)。
4.2016年12月31日之前:
上交、检查设计报告(地点:
计算机科学学院
实验机房)。
指导教师:
2015年11月20
日
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真3
《数据结构》课程设计
算术表达式语法检查
一目的
根据课题要求,完成算法表达式语法检查。
具体完成以下四点要求:
(1)键盘读入一个四则运算算术表达式,对其进行语法检查;
(2)算术表达式允许嵌
套,如果出错,指出出错位置;(3)不需要计算结果;(4)尽量不使用栈。
二需求分析
1、选择存放算术表达式的数据结构
本次课设,我选择了本学期数据结构中所学的栈来实现算术表达式中的字符存放。
2、运算符优先级划分
一个完整的算术表达式中包含+、-、*、/、(、)六种运算符,当遇到这些字符时要确
定其优先级的高低,并依次存放进栈或者出栈。
并且还可以进行发现输入错误提示判断,
达到课题中相关要求。
三概要设计
1、运算符优先级等级划分表
+
-
*
/
(
)
#
+
1
1
-1
-1
-1
1
1
-
1
1
-1
-1
-1
1
1
*
1
1
1
1
-1
1
1
/
1
1
1
1
-1
1
1
(
-1
-1
-1
-1
-1
0
-3
)
1
1
1
1
-1
1
1
#
-1
-1
-1
-1
-1
-2
0
上表中1代表栈中运算符出栈,进行运算;0代表栈中运算符(‘(’或‘#’)出
栈;-1代表当前运算符进栈;-2代表当前输入‘)’错误;-3代表算术表达式末尾少输
入‘)’。
2、程序流程图
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真4
《数据结构》课程设计
开始
输入一个算术表达式
定义一个栈A,用来存放数字;定义一个栈
B用来存放运算符
定义一个字符变量c,一个字符数组d[100]
从表达式首字符开始,获取一个字符存放
到c中,开始依次检查
c!
=’#’||
GetTob(B)!
=’#’否
是
结束
首字符是运算符
是
如果是’(’进栈,否则报错
否
是
检查下一个字符
字符是运算符
否
字符是数字
是
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真5
《数据结构》课程设计
数字放入字符数组d[100]
否是
检查下一个字符
字符是数字
否
将字符串数组d[100]转化
为数字,存入栈A
字符是运算符
是
字符是’(’
是
否
报错
判断运算符优
先级,将结果
否检查下一个字
放入b中
是
字符是运算符
否
跳出本次循环,进行
下一次循环
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真6
《数据结构》课程设计
b=1
是
A中最后进栈的两个数出栈,B
中最后进栈的运算符出栈,进
否行运算,运算结果存入栈A
跳出本次循环,进
行下一次循环
b=-1
是
运算符进栈B
否
进行下一个字符检查,若字符是
‘)’,报错。
检查下一个字符
否
字符是’(’
是
否运算符进栈
B
进行下一个字符检
报错
字符是运算符是
否
跳出本次循环,进
行下一次循环
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真7
《数据结构》课程设计
b=0是
否
B中运算符出栈
否进行下一个字符检查
跳出本次循环,进
行下一次循环
b=-2
否
b=-3
是
报错,输入’)’错误
进行下一个字符检查
跳出本次循环,进
行下一次循环
否
是
B中运算符出栈,并报
错。
第i位少输入’)’
报错,输入非法字符
跳出本次循环,进
行下一次循环
检查下一个字符
跳出本次循环,进行下
一次循环
结束
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真8
《数据结构》课程设计
四详细设计
1、栈的结构及相关功能函数构造伪代码
typedefintSElemType;
constintSTACK_INIT_SIZE=100;//存储空间初始分配量
constintSTACKINCREMENT=10;//存储空间分配增量
typedefstruct
{
SElemType*base;//栈底指针,在栈构造前和销毁后,其值均为空SElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间
}SqStack;
//构造一个空栈
voidInitStack(SqStack&S);
//若栈不为空,返回栈顶元素值
SElemTypeGetTop(SqStack&S);
//插入元素e为栈的新栈顶元素
voidpush(SqStack&S,SElemTypee);
//用e返回栈顶元素,并删除栈顶元素
voidPop(SqStack&S,SElemType&e);
2、实现表达式语法检查功能函数构造伪代码
//判定输入的运算符,并分类标记
intjudgePrecedence(chara)
{
inti=7;
switch(a)
{
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;
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真9
《数据结构》课程设计
}
returni;
}
//比较运算符的优先级,并标记分类
intPrecedence(chara,charb)
{
根据judgePrecedence()函数确定a、b的运算符种类,然后构建一个
7*7的
二维数组表,依次填入优先级,并返回相应优先等级。
具体表格信息见概要设计中
运算符优先等级划分表。
}
//执行运算
intOperate(inta,charb,intc)
{
其中a、c是数字,b是运算符(+、-、*、/),实现具体运算操作,并返回运算结果值。
}
//判断c是否是运算符
intpanduan(charc)
{
根据judgePrecedence()函数,判断c是否是运算符,如果是怎返回
1,否
则返回0。
}
//具体应用操作
voidYunsuan()
{
SqStackA,B;//创建栈A、B
push(B,'#');//栈B中栈底存入#
c=getchar();//获取算术表达式中字符
inti=1;
while(c!
='#'||GetTop(B)!
='#')
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真10
《数据结构》课程设计
{
if(i==1&&judgePrecedence(c)!
=7)
首字符是运算符,报错;
if(c>='0'&&c<='9')
字符是数字,存放在数组d[100]中,后转化为数字存入
栈A中;
elseif(judgePrecedence(c)!
=7)
字符是运算符,进行判断,有错则报错,没有则进栈B;
else
报错,输入非法字符。
}
}
五调试分析
1、算法逻辑问题及输出错误
检查一个算术表达式错误时,要具体要第几位以及是哪些错误,在刚开始的检查功能
检查设计的时候,我的代码只能检查到+、-、*、/相关输入错误,对于(、)运算符不能完
全检查出输入错误,其中有关除数为0的输入错误时,程序不能检查除数0后面表达式中
的错误,直接程序终止。
后来,我在程序加了一个条件关于除数为0的运算限定,成功解决了除数为0后面表
达式的语法无法检查的问题。
其中,最为重要的是,通过设计不同类型的算术表达式进行
语法检查,不断地发现程序设计过程中的逻辑错误,并不断修改,最后成功解决了本次课
设中难点。
六测试结果
1、设计输入的算术表达式
(1)+-*/1+2/(4-4*2/4)
(2)(3a+2b)*4-8/2
(3)a!
c1+2a*(3-4/2)
(4)1++2—3*(4//5)
(5)1+2*(2*4/0-3)
(6)1+2*(3-4/2
(7)1-2/((3-4*2)
(8)2*3+)(3/3-4)
(9)2++4-5*(3+2+((2*1)
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真11
《数据结构》课程设计
(10)(2++4))-5/0*(3+2*(2+1)
2、具体运算检查分析结果截图
图一:
上图一是设计输入的算术表达式
(1)—(4)运行结果截图;
图二:
上图二是设计输入的算术表达式(5)—(8)运行结果截图;
图三:
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真12
《数据结构》课程设计
上图三是输入设计的算术表达式(9)—(10)运行结果截图。
七用户使用说明
1、输入规则
输入一个算术表达式,其中对应的运算符是+、-、*、/、(、)表达的意思是加、减、
乘、除、顺括号、反括号。
要求输入一个算术表达式完毕后,在输入一个‘#’结束输入,最后按enter键即可得
到算术表达式语法检查结果。
八课程设计总结
在本次课程设计实施的过程中,遇到了很多问题,当然收获也很多。
起初,让我感觉很难的地方在于如何确定算术表达式错误的位置以及有哪些错误要确
定。
在此过程中,我用了一个整形变量来计算依次检查的字符数,来确定错误的具体位
置。
其中错误的类型要分类进行查找,在算法实施之前我把错误类型进行分类,并初步画
出算法的程序流程图,不断反复推敲和检查,从中也发现了我很多逻辑上的错误。
通过不断修改和测试,也让我设计的核心功能函数不断完善,最终达到课题的要求。
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真13
《数据结构》课程设计
附具体源码:
#include
#include
#include
usingnamespacestd;
typedefintSElemType;
constintSTACK_INIT_SIZE=100;//存储空间初始分配量
constintSTACKINCREMENT=10;//存储空间分配增量
typedefstruct
{
SElemType*base;//栈底指针,在栈构造前和销毁后,其值均为空SElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间
}SqStack;
//构造一个空栈
voidInitStack(SqStack&S);
//若栈不为空,返回栈顶元素值
SElemTypeGetTop(SqStack&S);
//插入元素e为栈的新栈顶元素
voidpush(SqStack&S,SElemTypee);
//用e返回栈顶元素,并删除栈顶元素
voidPop(SqStack&S,SElemType&e);
//判定输入的运算符,并分类标记
intjudgePrecedence(chara);
//比较运算符的优先级,并标记分类
intPrecedence(chara,charb);
//执行运算
intOperate(inta,charb,intc);
//判断c是否是运算符
intpanduan(charc);
//具体应用操作
voidYunsuan();
intmain()
{
while
(1)
{
cout<<"请输入算术表达式(按#结束):
";
中南民族大学计算机科学学院软件工程专业学号:
201421092073姓名:
柳真14
《数据结构》课程设计
Yunsuan();
/*cout<<"继续输入算术表达式请输入$,退出请输入#:
"< chari; cin>>i; if(i=='#') break;*/ } return0; } voidInitStack(SqStack&S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));S.top=S.base; S.stacksize=STACK_INIT_SIZE; return; } SElemTypeGetTop(SqStack&S) { if(S.top==S.base)return0; return*(S.top-1); } voidpush(SqStack&S,SElemTypee) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(! S.base)exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return; } voidPop(SqStack&S,SElemType&e) { if(S.top==S.base)return; 中南民族大学计算机科学学院软件工程专业学号: 201421092073姓名: 柳真15 《数据结构》课程设计 e=*--S.top; return; } intjudgePrecedence(chara) { inti=7; switch(a) { 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; } returni; } intPrecedence(chara,charb) { inti,j; i=judgePrecedence(a); j=judgePrecedence(b); intPre[7][7]={ {1,1,-1,-1,-1,1,1}, {1,1,-1,-1,-1,1,1}, {1,1,1,1,-1,1,1}, {1,1,1,1,-1,1,1}, {-1,-1,-1,-1,-1,0,-3}, {1,1,1,1,-1,1,1}, {-1,-1,-1,-1,-1,-2,0} }; if(Pre[i][j]==1) return1; elseif(Pre[i][j]==-1) return-1; elseif(Pre[i][j]==-2) return-2; elseif(Pre[i][j]==-3) 中南民族大学计算机科学学院软件工程专业学号: 201421092073姓名: 柳真16 《数据结构》课程设计 return-3; else return0; } intOperate(inta,charb,intc) { switch(b) { case'+': returna+c;break; case'-': returna-c;break; case'*': returna*c;break; case'/': if(c==0) return1; else returna/c; break; } return0; } intpanduan(charc) { inti=0; if(judgePrecedence(c)! =7) i=1; returni; } voidYunsuan() { SqStackA,B; inta,b,e; charc,d[100]; InitStack(A); InitStack(B); push(B,'#'); c=getchar(); inti=1; while(c! ='#'||GetTop(B)! ='#') 中南民族大学计算机科学学院软件工程专业学号: 201421092073姓名: 柳真17 《数据结构》课程设计 { intt=0; if(i==1&&judgePrecedence(c)! =7) { if(judgePrecedence(c)==4) { push(B,c); c=getchar(); ++i; } else { cout<<"第1位输入"< c=getchar(); ++i; while(panduan(c)) { cout<<"第"< c=getchar(); ++i; } } } if(c>='0'&&c<='9') { while(c>='0'&&c<='9') { d[t++]=c; c=getchar(); ++i; } d[t]='\0'; a=atoi(d);//字符型转换为整形 push(A,a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 表达式 语法 检查 数据结构 课程设计