计算机工程学院
课程设计报告
课程名称：数据结构课程设计
设计题目：括号匹配问题
院系：计算机工程学院
专业：
组别：
学生姓名: 学号:
起止日期:年月日~年月日
指导教师:
目录
1.需求分析 (2)
1.1课程设计题目 (2)
1.2 课程设计任务及要求 (2)
1.3 课程设计思想 (2)
1.4软硬件运行环境及开发工具 (2)
1.概要设计 (2)
2.1课题设计的流程图 (2)
2.2主要的数据结构 (3)
3.详细设计 (4)
3.1课题设计的方法及原理 (4)
3.2主要代码实现 (4)
4.调试与操作说明 (5)
5.总结与体会 (6)
6.致谢 (7)
7．参考文献 (7)
1.需求分析
1.1课程设计题目
括号匹配问题
1.2 课程设计任务及要求
假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。
1.3 课程设计思想
利用栈来判断括号是否匹配时，遇到左括号就进栈，遇到右括号则左括号出栈，代表这对括号匹配，如果右括号进栈时，栈为空，则说明缺少左括号，若表达式扫描完栈为空，则说明表达式的括号匹配，否则说明表达式缺少左括号。
1.4软硬件运行环境及开发工具
Microsoft visual C++ 6.0
1.概要设计
2.1课题设计的流程图
2.2主要的数据结构
栈类包括如下数据成员和成员函数
top; //指向栈顶的指针
LinkStack(); //构造函数
bool isEmpty(); //判断栈是否为空
void Push(T x); //x进栈，top指向x
T Pop(); //栈顶元素出栈
T GetPop(); / /读取栈顶元素
bool Search(T x); //搜素栈中是否有x这个元素
void OutPut(); //输出栈内所有元素
3.详细设计
3.1课题设计的方法及原理
1）定义三个栈 s1,s2,s3分别用来判断圆括号，方括号和花括号是否匹配
2）对s1,s2,s3均有如下操作：
a.利用动态指针p依次对输入的（字符串）表达式进行扫
描
I.若为左括号，则进栈
II若为右括号，则先取栈顶元素。若栈顶元素为空，则缺少左括号；若不为空，则栈顶元素出栈
b.当字符串扫描完，检验栈是否为空。若为空，则括号正确
匹配。否则表示缺少右括号
3.2主要代码实现
sign1 ,sign2 ,sign3是分别用来标记栈是否为空
while(*p!='#')
{
switch(*p)
{
case'(':
s1.Push(*p);
break;
case')':
if(s1.isEmpty())
{
sign1=false;
cout<<"缺少'('"<}
else
s1.Pop();
break;
case'[':
s2.Push(*p);
break;
case']':
if(s2.isEmpty())
{
sign2=false;
cout<<"缺少'['"<}
else
s2.Pop();
break;
case'{':
s3.Push(*p);
break;
case'}':
if(s3.isEmpty())
{
sign3=false;
cout<<"缺少'{'"<}
else
s3.Pop();
break;
default:
break;
}
p++;
}
4.调试与操作说明
检验圆括号是否正确匹配
检验方括号是否正确匹配
综合检验三种括号是否正确匹配
5.
6.致谢
。。。。。。
7．参考文献
数据结构（C++版）叶核亚主编机械工业出版社
数据结构陈本林主编南京大学出版社
数据结构（用面向对象方法与C++语言描述）殷人昆主编清华大学出版社
