《数据结构课程设计-括号匹配》由会员分享，可在线阅读，更多相关《数据结构课程设计-括号匹配（26页珍藏版）》请在金锄头文库上搜索。
1、目 录1 问题描述21.1题目21.2问题21.3要求22 设计22.1存储结构设计22.2主要算法设计32.3测试用例及测试结果63 调试报告94 对设计和编码的讨论和分析204.1设计204.2对编码的讨论215 总结和体会22附录一24本科生课程设计成绩评定表27数据结构课程设计 判别括号配对1问题描述1.1题目：判别括号配对1.2问题：一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。1.3要求：（1）表达式从键盘输入。（2）利用栈求解此问题。（3）测试用例自己设计。2设计2.1存储结构设计题目要求利用栈来求解此问题，因此
2、选择顺序栈作为存储结构，具体表示如下：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack;2.2主要算法设计算法思想(1) 文字描述从键盘输入一个表达式；逐个扫描表达式中的字符；当遇到左括号时，将左括号入栈； 继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈； 否则，继续扫描； 当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配； 若栈为空，则括号配对成功； 在括号配对不成功的情况下，利用栈顶
3、栈底元素的差值，可以对左右括号数进行比较。（2）流程图表示从键盘输入一个表达式扫描表达式中的一个字符左括号? 左括号入栈N 右括号?Y YN是否匹配Y 左括号出栈N计数器加1扫描结束?NY计数器为0,且栈为空?匹配成功，输出结果Y匹配不成功，输出左右括号差N算法 void CharIsCorrect(char a)SqStack S;char e;int n,c;InitStack(S);/建立一个空栈 n=strlen(a);/求表达式长度 int d=0,b=0; for(int i=0;in;i+) if(ai=()|(ai=)|(ai=) Push(S,ai); else c=Stac
4、kEmpty(S); if (c=1)&(ai=)|(ai=)|(ai=)/栈为空且当前扫描的字符为右括号时，右括号多于左括号 +b; else e=GetTop(S); if (ai=)&(e=()|(ai=)&(e=)|(ai=)&(e=)/括号匹配时满足的条件 e=Pop(S); else if (ai=)|(ai=)|(ai=)+d; /扫描字符串，左括号进栈，右括号出栈 if(StackEmpty(S)=1&(b=0)&(d=0) cout左右括号配对正确endl;/栈为空时，括号匹配 else cout左右括号不匹配且左括号与右括号个数差为S.top-S.base-d-b个endl
5、;/正数表示左括号比右括号多，负数则相反2.3测试用例及测试结果（1）表达式不含除括号外其他字符，配对正确的情况：（2）表达式不含除括号外其他字符且左括号少于右括号的情况：（3）表达式含任意字符且左括号少于右括号的情况：（4）表达式含任意字符且左右括号个数相同但配对不成功的情况：（5）表达式仅含括号且括号个数相同单不匹配的情况：（6）表达式仅含括号且左括号对于右括号的情况：3调试报告1.本次课程设计，主要的调试过程在于对于判别函数的调试，但是除此之外，由于编译过程中发现了一些错误，对于栈的一些基本操作，以及main函数，也进行了调试，其中遇到的主要问题如下：(1)大小写出错解决办法：将所有小写
6、s改为大写S 即可。(2)在写“判断栈是否为空”的操作时，将函数的类型标示符写错，导致了如下错误：解决办法：将“void”改为“int”后，能够正常运行。(3)判断配对函数中的形参是字符数组，但是从键盘中输入的是字符串，因此在主函数中，当用cin进行输入时出错：解决办法：将char a 改为char a20 后编译不出现错误。(4)除了以上错误之外，还有一些小错误，编号如下：Error C 2146、 error C 2143、 error C 2109 等等，一般再仔细检查后，能够检出错误。2.以下，对主要程序进行调试，过程如下：(1)第一次成型的主体部分代码如下：void CharIsCo
7、rrect(char a)SqStack S;char e;int n,c;InitStack(S);/建立一个空栈 n=strlen(a);/求表达式长度 int m=0; for(int i=0;i=n;i+) if(ai=()|(ai=)|(ai=) Push(S,ai); else c=StackEmpty(S); if (c=1)&(ai=)|(ai=)|(ai=)/栈为空且当前扫描的字符为右括号时，右括号多于左括号 +m; else e=GetTop(S); while (ai=)&(e=()|(ai=)&(e=)|(ai=)&(e=)/括号匹配时满足的条件 e=Pop(S); /
8、扫描字符串，左括号进栈，右括号出栈 if(!m=0)cout左右括号不匹配且左括号比右括号少endl;/栈不为空时，左括号多于右括号 else if(StackEmpty(S)=1) cout左右括号匹配正确endl;/栈为空时，括号匹配 else cout左右括号不匹配且左括号比右括号多endl; 运行结果不正确，结果如下用能够成功配对的两对括号进行测试，测试结果应为“左右括号配对成功”，但测试结果实际为“左右括号不匹配且左括号比右括号少”，测试结果不正确：找到导致错误的原因是while ，while执行了两次，使栈为空。将while 改为 if 后，问题得到解决。同时为了提高程序的有效性，
9、在出栈时也设了计数器，同时用左括号与右括号的个数差来表示左右括号的多少，正负数区别左右括号总数谁多谁少（正数左括号多，负数右括号多）。(2)第二次修改此时，主体部分修改结果如下：void CharIsCorrect(char a)SqStack S;char e;int n,c;InitStack(S);/建立一个空栈 n=strlen(a);/求表达式长度 int d=0,b=0; for(int i=0;in;i+) if(ai=()|(ai=)|(ai=) Push(S,ai); else c=StackEmpty(S); if (c=1)&(ai=)|(ai=)|(ai=)/栈为空且当
10、前扫描的字符为右括号时，右括号多于左括号 +b; else e=GetTop(S); if (ai=)&(e=()|(ai=)&(e=)|(ai=)&(e=)/括号匹配时满足的条件 e=Pop(S); else +d; /扫描字符串，左括号进栈，右括号出栈 if(StackEmpty(S)=1&(b=0)&(d=0) cout左右括号配对正确endl;/栈为空时，括号匹配 else cout左右括号不匹配且左括号与右括号个数差为S.top-S.base-d-b个endl;/正数表示左括号比右括号多，负数则相反 此时，对仅含有括号的表达式进行测试时，未发现任何问题，但在测试含有字母数字等不仅仅只
11、有括号的表达式时，出现错误测试结果如下：输入含有字母的表达式，正确的测试结果为“左右括号不匹配且左括号与右括号个数差为-2”，但实际测试结果如下，测试结果不正确：这是由于在不匹配的情况下，将所有的字符一概视为右括号所致，因此最后一个else分支处应加上if限制条件，在仅出现不匹配的右括号时，计数器的值才发生改变，因此将代码做如下修改：(3)第三次修改：void CharIsCorrect(char a)SqStack S;char e;int n,c;InitStack(S);/建立一个空栈 n=strlen(a);/求表达式长度 int d=0,b=0; for(int i=0;in;i+) if(ai=()|(ai=)|(ai=) Push(S,ai); else c=StackEmpty(S); if (c=
