欢迎来到天天文库
浏览记录
ID:47518114
大小:1022.51 KB
页数:26页
时间:2020-01-12
《数据结构课程设计---括号匹配》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、武汉理工大学《数据结构》课程设计说明书目录1问题描述21.1题目21.2问题21.3要求22设计22.1存储结构设计22.2主要算法设计32.3测试用例及测试结果63调试报告94对设计和编码的讨论和分析204.1设计204.2对编码的讨论215总结和体会22附录一24本科生课程设计成绩评定表2726武汉理工大学《数据结构》课程设计说明书数据结构课程设计——判别括号配对1问题描述1.1题目:判别括号配对1.2问题:一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序,判断任一算术表达式中
2、所含括号是否正确配对。1.3要求:(1)表达式从键盘输入。(2)利用栈求解此问题。(3)测试用例自己设计。2设计2.1存储结构设计题目要求利用栈来求解此问题,因此选择顺序栈作为存储结构,具体表示如下:#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{26武汉理工大学《数据结构》课程设计说明书char*base;char*top;intstacksize;}SqStack;2.2主要算法设计2.2.1算法思想(1)文字描述从键盘输入
3、一个表达式;逐个扫描表达式中的字符;当遇到左括号时,将左括号入栈;继续扫描,将此后遇到的第一个右括号与栈顶元素比较,若匹配,则栈顶元素出栈;否则,继续扫描;当整个表达式扫描完以后,判断栈内是否还有元素,若有,则括号不匹配;若栈为空,则括号配对成功;在括号配对不成功的情况下,利用栈顶栈底元素的差值,可以对左右括号数进行比较。(2)流程图表示26武汉理工大学《数据结构》课程设计说明书从键盘输入一个表达式扫描表达式中的一个字符左括号?左括号入栈N右括号?YYN是否匹配Y左括号出栈N计数器加1扫描结束?NY计数
4、器为0,且栈为空?匹配成功,输出结果Y匹配不成功,输出左右括号差N26武汉理工大学《数据结构》课程设计说明书2.2.2算法voidCharIsCorrect(chara[]){SqStackS;chare;intn,c;InitStack(S);//建立一个空栈n=strlen(a);//求表达式长度intd=0,b=0;for(inti=0;i5、6、(a[i]=='[')7、8、(a[i]=='{'))Push(S,a[i]);else{c=StackEmpty(9、S);if((c==1)&&((a[i]==')')10、11、(a[i]==']')12、13、(a[i]=='}')))//栈为空且当前扫描的字符为右括号时,右括号多于左括号++b;else{e=GetTop(S);if(((a[i]==')')&&(e=='('))14、15、((a[i]==']')&&(e=='['))16、17、((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件e=Pop(S);elseif((a[i]==')')18、19、(a[i]==']')20、21、(a[i]=='}'))++d;}}26武22、汉理工大学《数据结构》课程设计说明书}//扫描字符串,左括号进栈,右括号出栈if(StackEmpty(S)==1&&(b==0)&&(d==0))cout<<"左右括号配对正确"<23、不含除括号外其他字符且左括号少于右括号的情况:(3)表达式含任意字符且左括号少于右括号的情况:26武汉理工大学《数据结构》课程设计说明书(4)表达式含任意字符且左右括号个数相同但配对不成功的情况:(5)表达式仅含括号且括号个数相同单不匹配的情况:26武汉理工大学《数据结构》课程设计说明书(6)表达式仅含括号且左括号对于右括号的情况:3调试报告1.本次课程设计,主要的调试过程在于对于判别函数的调试,但是除此之外,由于编译过程中发现了一些错误,对于栈的一些基本操作,以及main函数,也进行了调试,其中遇到的24、主要问题如下:(1)大小写出错26武汉理工大学《数据结构》课程设计说明书解决办法:将所有小写s改为大写S即可。(2)在写“判断栈是否为空”的操作时,将函数的类型标示符写错,导致了如下错误:解决办法:将“void”改为“int”后,能够正常运行。(3)判断配对函数中的形参是字符数组,但是从键盘中输入的是字符串,因此在主函数中,当用cin进行输入时出错:26武汉理工大学《数据结构》课程设计说明书解决办法:将chara改为chara[20]后编译
5、
6、(a[i]=='[')
7、
8、(a[i]=='{'))Push(S,a[i]);else{c=StackEmpty(
9、S);if((c==1)&&((a[i]==')')
10、
11、(a[i]==']')
12、
13、(a[i]=='}')))//栈为空且当前扫描的字符为右括号时,右括号多于左括号++b;else{e=GetTop(S);if(((a[i]==')')&&(e=='('))
14、
15、((a[i]==']')&&(e=='['))
16、
17、((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件e=Pop(S);elseif((a[i]==')')
18、
19、(a[i]==']')
20、
21、(a[i]=='}'))++d;}}26武
22、汉理工大学《数据结构》课程设计说明书}//扫描字符串,左括号进栈,右括号出栈if(StackEmpty(S)==1&&(b==0)&&(d==0))cout<<"左右括号配对正确"<23、不含除括号外其他字符且左括号少于右括号的情况:(3)表达式含任意字符且左括号少于右括号的情况:26武汉理工大学《数据结构》课程设计说明书(4)表达式含任意字符且左右括号个数相同但配对不成功的情况:(5)表达式仅含括号且括号个数相同单不匹配的情况:26武汉理工大学《数据结构》课程设计说明书(6)表达式仅含括号且左括号对于右括号的情况:3调试报告1.本次课程设计,主要的调试过程在于对于判别函数的调试,但是除此之外,由于编译过程中发现了一些错误,对于栈的一些基本操作,以及main函数,也进行了调试,其中遇到的24、主要问题如下:(1)大小写出错26武汉理工大学《数据结构》课程设计说明书解决办法:将所有小写s改为大写S即可。(2)在写“判断栈是否为空”的操作时,将函数的类型标示符写错,导致了如下错误:解决办法:将“void”改为“int”后,能够正常运行。(3)判断配对函数中的形参是字符数组,但是从键盘中输入的是字符串,因此在主函数中,当用cin进行输入时出错:26武汉理工大学《数据结构》课程设计说明书解决办法:将chara改为chara[20]后编译
23、不含除括号外其他字符且左括号少于右括号的情况:(3)表达式含任意字符且左括号少于右括号的情况:26武汉理工大学《数据结构》课程设计说明书(4)表达式含任意字符且左右括号个数相同但配对不成功的情况:(5)表达式仅含括号且括号个数相同单不匹配的情况:26武汉理工大学《数据结构》课程设计说明书(6)表达式仅含括号且左括号对于右括号的情况:3调试报告1.本次课程设计,主要的调试过程在于对于判别函数的调试,但是除此之外,由于编译过程中发现了一些错误,对于栈的一些基本操作,以及main函数,也进行了调试,其中遇到的
24、主要问题如下:(1)大小写出错26武汉理工大学《数据结构》课程设计说明书解决办法:将所有小写s改为大写S即可。(2)在写“判断栈是否为空”的操作时,将函数的类型标示符写错,导致了如下错误:解决办法:将“void”改为“int”后,能够正常运行。(3)判断配对函数中的形参是字符数组,但是从键盘中输入的是字符串,因此在主函数中,当用cin进行输入时出错:26武汉理工大学《数据结构》课程设计说明书解决办法:将chara改为chara[20]后编译
此文档下载收益归作者所有