数据结构课程设计---括号匹配.doc

目 录

1 问题描述 2
1.1题目 2
1.2问题 2
1.3要求 2

2 设计 2
2.1存储结构设计 2
2.2主要算法设计 3
2.3测试用例及测试结果 6

3 调试报告 9

4 对设计和编码的讨论和分析 20
4.1设计 20
4.2对编码的讨论 21

5 总结和体会 22

附录一 24

本科生课程设计成绩评定表 27

数据结构课程设计
——判别括号配对

1问题描述
1.1题目：
判别括号配对

1.2问题：
一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。

1.3要求：
（1）表达式从键盘输入。
（2）利用栈求解此问题。
（3）测试用例自己设计。

2设计

2.1存储结构设计
题目要求利用栈来求解此问题，因此选择顺序栈作为存储结构，具体表示如下：

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;

2.2主要算法设计

2.2.1算法思想

(1) 文字描述

从键盘输入一个表达式；
逐个扫描表达式中的字符；
当遇到左括号时，将左括号入栈；
继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈；
否则，继续扫描；
当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配；
若栈为空，则括号配对成功；
在括号配对不成功的情况下，利用栈顶栈底元素的差值，可以对左右括号数进行比较。

（2）流程图表示

从键盘输入一个表达式
扫描表达式中的一个字符
左括号?
左括号入栈
N

右括号?
Y

Y
N
是否匹配
Y

左括号出栈
N
计数器加1
扫描结束?
N
Y
计数器为0,且栈为空?
匹配成功，输出结果
Y
匹配不成功，输出左右括号差
N

2.2.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;i<n;i++){
if((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))
Push(S,a[i]);
else{
c=StackEmpty(S);
if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号
++b;
else{
e=GetTop(S);
if (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件
e=Pop(S);
else if ((a[i]==')')||(a[i]==']')||(a[i]=='}'))
++d;
}

}
}//扫描字符串，左括号进栈，右括号出栈

if(StackEmpty(S)==1&&(b==0)&&(d==0))
cout<<"左右括号配对正确"<<endl;//栈为空时，括号匹配
else cout<<"左右括号不匹配且左括号与右括号个数差为"<<S.top-S.base-d-b<<"个"<<endl;//正数表示左括号比右括号多，负数则相反

}

2.3测试用例及测试结果

（1）表达式不含除括号外其他字符，配对正确的情况：

（2）表达式不含除括号外其他字符且左括号少于右括号的情况：

（3）表达式含任意字符且左括号少于右括号的情况：

（4）表达式含任意字符且左右括号个数相同但配对不成功的情况：

（5）表达式仅含括号且括号个数相同单不匹配的情况：

（6）表达式仅含括号且左括号对于右括号的情况：

3调试报告

1.本次课程设计，主要的调试过程在于对于判别函数的调试，但是除此之外，由于编译过程中发现了一些错误，对于栈的一些基本操作，以及main函数，也进行了调试，其中遇到的主要问题如下：
(1)大小写出错

解决办法：将所有小写s改为大写S 即可。

(2)在写“判断栈是否为空”的操作时，将函数的类型标示符写错，导致了如下错误：

解决办法：将“void”改为“int”后，能够正常运行。

(3)判断配对函数中的形参是字符数组，但是从键盘中输入的是字符串，因此在主函数中，当用cin进行输入时出错：

解决办法：将char a 改为char a[20] 后编译不出现错误。

(4)除了以上错误之外，还有一些小错误，编号如下：
Error C 2146、 error C 2143、 error C 2109 等等，一般再仔细检查后，能够检出错误。

2.以下，对主要程序进行调试，过程如下：
(1)第一次成型的主体部分代码如下：
void CharIsCorrect(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((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))
Push(S,a[i]);
else{
c=StackEmpty(S);
if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号
++m;
else{
e=GetTop(S);
while (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件
e=Pop(S);

}

}
}//扫描字符串，左括号进栈，右括号出栈

if(!m==0)cout<<"左右括号不匹配且左括号比右括号少"<<endl;//栈不为空时，左括号多于右括号
else{
if(StackEmpty(S)==1)
cout<<"左右括号匹配正确"<<endl;//栈为空时，括号匹配
else cout<<"左右括号不匹配且左括号比右括号多"<<endl;
}

}
运行结果不正确，结果如下

用能够成功配对的两对括号进行测试，测试结果应为“左右括号配对成功”，但测试结果实际为“左右括号不匹配且左括号比右括号少”，测试结果不正确：

找到导致错误的原因是while ，while执行了两次，使栈为空。将while 改为 if 后，问题得到解决。
同时为了提高程序的有效性，在出栈时也设了计数器，同时用左括号与右括号的个数差来表示左右括号的多少，正负数区别左右括号总数谁多谁少（正数左括号多，负数右括号多）。

(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;i<n;i++){
if((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))
Push(S,a[i]);
else{
c=StackEmpty(S);
if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号
++b;
else{
e=GetTop(S);
if (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(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;//正数表示左括号比右括号多，负数则相反
}

此时，对仅含有括号的表达式进行测试时，未发现任何问题，但在测试含有字母数字等不仅仅只有括号的表达式时，出现错误测试结果如下：

输入含有字母的表达式，正确的测试结果为“左右括号不匹配且左括号与右括号个数差为-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;i<n;i++){
if((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))
Push(S,a[i]);
else{
c=StackEmpty(S);
if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号
++b;
else{
e=GetTop(S);
if (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件
e=Pop(S);
else if ((a[i]==')')||(a[i]==']')||(a[i]=='}'))
++d;
}

}
}//扫描字符串，左括号进栈，右括号出栈

if(StackEmpty(S)==1&&(b==0)&&(d==0))
cout<<"左右括号配对正确"<<endl;//栈为空时，括号匹配
else cout<<"左右括号不匹配且左括号与右括号个数差为"<<S.top-S.base-d-b<<"个"<<endl;//正数表示左括号比右括号多，负数则相反

}

再次进行测试，测试结果均正确，结果如下：

（1）表达式仅含括号且配对正确：

（2）表达式仅含括号且左括号少于又括号：

（3）表达式含字母和括号且左括号少于右括号：

（4）表达式含任意字符且左右括号个数相同但不匹配：

（5）表达式仅含括号且括号个数相同但不匹配：

（6）表达式仅含括号且左括号比右括号多：

至此，调试成功，所编写的代码符合题目要求！

4.对设计和编码的讨论和分析

4.1设计
对于从键盘输入的表达式，其括号配对情况有以下四种：
a.表达式括号配对成功
b.表达式括号配对不成功但左右括号个数相等
c.表达式括号配对不成功且左括号比右括号的个数多
d.表达式括号配对不成功且左括号个数比右括号少

因此，对于一个表达式，要判别其括号配对情况，必会得到这四种中的某一种结果，根据每种结果不同于其他结果的特点，分离出该种表达式，从而给出相应的配对结果。

4.2对编码的讨论
对于顺序栈这种存储结构，在本次课程设计中要用到许多它的操作。具体如下：

（1）建立一个空栈
void InitStack(SqStack &S){
S.base=(char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!S.base)exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}

（2）入栈操作
void Push(SqStack &S,char e){
if(S.top-S.base>=S.stacksize){
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}

（3）出栈操作
char Pop(SqStack &S){
if(S.top==S.base) return 0;
return *--S.top;

}

（4）取栈顶元素
char GetTop(SqStack S){
if(S.base==S.top) return 0;
return *(S.top-1);
}

（5）判断栈是否为空
int StackEmpty(SqStack S){
if(S.base==S.top) return 1;
return 0;
}

5 总结和体会
《数据结构》是物联网工程专业的专业基础课，也是软件设计的技术基础。《数据结构》课程的教学要求之一是训练我们进行复杂的程序设计的技能和培养良好程序设计的风格，其重要程度不亚于理论知识的传授，因此课程设计环节是一个至关重要的环节，是培养创新意识和创新能力的极为重要的环节。
在本次课程设计过程中，我收获颇丰：
1. 在开始设计程序，写算法，编写代码实现问题求解之前，我查阅了有关“判别括号配对”的资料，让我在准备的过程中培养了搜索和收集信息的能力，让我学会取其精华去其糟粕，在长篇大论的理论材料中寻找我所需要的信息。同时，在接受前人思想的基础上，能够学会创新，想别人想不到的，做出和别人不一样的东西。
2. 在搜集到资料以后，开始着手对我所要研究的问题进行深入的分析，在一遍一遍修改算法的过程中，去寻找一种最简洁最高效最可行的最优解。在这一过程中，我学会了将一个复杂的问题分解成几部分，逐个击破，逐个完成，当每一部分都完成以后，再将所有的拼接起来。也要能够找出这个复杂问题中的核心部分（在本题中，最核心的部分就是如何写出一个最优的判别函数），将重点放在这一部分，其他的部分有所兼顾到就行。
3. 编写程序实现算法的时候，是最考验一个人思维严密性的时候，既要考虑到符合这一条件的情况有哪些，还要考虑到怎样处理不符合条件的情况，在逻辑上，需要有很好的逻辑思维。其次在调试程序的时候，也需要我们耐心细心的完成，有时候出现错误的可能只是一个标点符号，但却能影响整个程序是否能够正常运行。这也是编程的时候老师常和我们说的，一个好的程序应具有的正确性，可读性和健壮性。
4. 在完成一个程序以后，我们还应该思考，有没有什么更好的办法，可以让这个程序实现更多的功能，在解决已有问题的基础上，提供更多的信息。如果没有，怎样又可以让现有的程序更加的简洁，易于理解，运行起来更加顺畅，占用更少的内存空间等等。
5. 这次课程设计，对我帮助最大的一点就是对于数据结构这门课程的理解以及熟悉。在理论知识的学习阶段，很多知识我都只能泛泛的了解点皮毛，没有自己深刻的见解。借着这次课程设计的机会，我又将数据结构系统而又细致的看了一遍，不仅对以前所学的部分知识有了新的认识，在编程过程中，对于栈这一种数据结构更是有了深入的理解，并且能够很好的加以运用。以前的认识都只是停留在呆板的记忆层面，通过课程设计，我将以前所学的知识学活了，因为能够熟练的运用而更加的了解。
总而言之，这次的课程设计对我来说意义深远，让我从中受益匪浅。每一门课程的最终作用都是让我们能够学会运用，而课程设计的意义正在于此，这是我们将理论知识运用到实践中的最好的机会，在探索中学习，在实践中锻炼自己！

附录一：

完整代码如下：

#include<string.h>
#include<stdio.h>
#include<iostream>
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;

void InitStack(SqStack &S){
S.base=(char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!S.base)exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}

void Push(SqStack &S,char e){
if(S.top-S.base>=S.stacksize){
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}

char Pop(SqStack &S){
if(S.top==S.base) return 0;
return *--S.top;

}

char GetTop(SqStack S){
if(S.base==S.top) return 0;
return *(S.top-1);
}

int StackEmpty(SqStack S){
if(S.base==S.top) return 1;
return 0;
}

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;i<n;i++){
if((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))
Push(S,a[i]);
else{
c=StackEmpty(S);
if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号
++b;
else{
e=GetTop(S);
if (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(e=='{')))//括号匹配时满足的条件
e=Pop(S);
else if ((a[i]==')')||(a[i]==']')||(a[i]=='}'))++d;
}

}
}//扫描字符串，左括号进栈，右括号出栈

if(StackEmpty(S)==1&&(b==0)&&(d==0))
cout<<"左右括号配对正确"<<endl;//栈为空时，括号匹配
else cout<<"左右括号不匹配且左括号与右括号个数差为"<<S.top-S.base-d-b<<"个"<<endl;//正数表示左括号比右括号多，负数则相反
}

void main(){
char a[20];
cout<<"请输入表达式："<<endl;
gets(a);

CharIsCorrect(a);
}

THANKS !!!

致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求

欢迎您的下载，资料仅供参考