算法表达式语法检查数据结构课程设计.docx
《算法表达式语法检查数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《算法表达式语法检查数据结构课程设计.docx（24页珍藏版）》请在冰点文库上搜索。
算法表达式语法检查数据结构课程设计
中南民族大学
计算机科学学院
课程设计报告
课程数据结构
题目算法表达式语法检查
年级2014
专业软件工程
学生柳真
学号201421092073
指导教师刘赛
2015年12月20日
中南民族大学计算机科学学院本科课程设计
任务书
设计名称：
算术表达式语法检查
指导教师：
下达时间：
2015-11-30
学生姓名：
学号：
年级专业：
2014级软件工程
一、课程设计的基本要求
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。
通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。
具体要求如下：
1、对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理。
2、采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。
学生也可根据自己对题目的理解增加新的功能模块（视情况可另外加分）。
3、系统以菜单界面方式（至少采用文本菜单界面，如能采用图形菜单界面更好）工作，运行界面友好，演示程序以用户和计算机的对话方式进行，利用文件进行数据的提取与存储。
4、程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强（能对错误输入进行判断控制）。
5、编程风格良好（包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等）；
6、写出规范的课程设计报告，具体要求见相关说明文档。
二、课程设计的主要内容
题目描述：
算术表达式语法检查。
功能要求及说明：
（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日
算术表达式语法检查
一目的
根据课题要求，完成算法表达式语法检查。
具体完成以下四点要求：
（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、程序流程图
四详细设计
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;
}
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）!
='#'）
{
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）
（10）（2++4））-5/0*（3+2*（2+1）
2、具体运算检查分析结果截图
图一：
上图一是设计输入的算术表达式
（1）—（4）运行结果截图；
图二：
上图二是设计输入的算术表达式（5）—（8）运行结果截图；
图三：
上图三是输入设计的算术表达式（9）—（10）运行结果截图。
七用户使用说明
1、输入规则
输入一个算术表达式，其中对应的运算符是+、-、*、/、（、）表达的意思是加、减、乘、除、顺括号、反括号。
要求输入一个算术表达式完毕后，在输入一个‘#’结束输入，最后按enter键即可得到算术表达式语法检查结果。
八课程设计总结
在本次课程设计实施的过程中，遇到了很多问题，当然收获也很多。
起初，让我感觉很难的地方在于如何确定算术表达式错误的位置以及有哪些错误要确定。
在此过程中，我用了一个整形变量来计算依次检查的字符数，来确定错误的具体位置。
其中错误的类型要分类进行查找，在算法实施之前我把错误类型进行分类，并初步画出算法的程序流程图，不断反复推敲和检查，从中也发现了我很多逻辑上的错误。
通过不断修改和测试，也让我设计的核心功能函数不断完善，最终达到课题的要求。
附具体源码：
#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<<"请输入算术表达式（按#结束）：
";
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;
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）
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）!
='#'）
{
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）;
}
elseif（judgePrecedence（c）!
=7）
{
if（judgePrecedence（c）==4）
{
cout<<"第"<c=getchar（）;
++i;
while（panduan（c））
{
cout<<"第"<c=getchar（）;
++i;
}
break;
}
b=Precedence（GetTop（B）,c）;
switch（b）
{
case1:
Pop（A,b）;Pop（A,a）;Pop（B,e）;
if（e=='/'&&b==0）
cout<<"第"<<（i-1）<<"位非法输入，除数不能为0！
！
！
"<push（A,Operate（a,e,b））;
break;
case-1:
push（B,c）;
c=getchar（）;
++i;
if（c=='）'）
{
cout<<"第"<c=getchar（）;
++i;
}
if（c=='（'）
{
push（B,c）;
c=getchar（）;
++i;
}
while（panduan（c））
{
cout<<"第"<c=getchar（）;
++i;
}
break;
case0:
Pop（B,e）;
c=getchar（）;
++i;
break;
case-2:
cout<<"第"<c=getchar（）;
++i;
break;
case-3:
Pop（B,e）;
cout<<"第"<break;
}
}
else
{
cout<<"第"<c=getchar（）;
++i;
}
}
c=getchar（）;
cout<<"算术表达式语法检查完毕，已退出！
！
！
";
cout<}
升级会员 