括号匹配

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：自动括号匹配器的

设计

院（系）：信息学院

专 业：计算机科学与技术 班 级：091 学 号：26 姓 名：张燕 指导教师：刘娜

沈阳航空航天大学课程设计报告

目 录

沈阳航空航天大学 ........................................................................ 错误！未定义书签。 1 需求分析 .................................................................................................................... 1 1.1 问题描述 ................................................................................................................ 1 1.2 问题理解 ................................................................................................................ 1 2 系统设计 .................................................................................................................... 2 2.1 总体方案设计 ........................................................................................................ 2 2.2 数据结构设计 ........................................................................................................ 2 2.3 函数设计 ................................................................................................................ 3 2.4 关键流程 ................................................................................................................ 4 2.4.1 系统主流程 ..................................................................................................... 4 2.4.2 构造一个空栈函数流程 ................................................................................. 5 2.4.3 插入元素e为栈顶函数流程 ......................................................................... 5 2.4.4 栈顶元素e出栈函数流程 ............................................................................. 7 2.4.5判断栈是否为空函数 ...................................................................................... 8 2.4.6把栈重置为空函数 .......................................................................................... 8 2.4.7销毁已存在的栈函数 ...................................................................................... 9 2.4.8根据括号出现的情况，判断是否匹配函数 ................................................ 10 3 调试分析 .................................................................................................................. 12 4 测试及运行结果 ...................................................................................................... 13 参考文献 ........................................................................................................................ 17

附 录 .......................................................................................................................... 18

I

沈阳航空航天大学课程设计报告

1 需求分析

1.1 问题描述

设计一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确匹配出现的算法。

1.2 问题理解

判断给定表达式中所含括号是否正确匹配出现的算法，应该利用栈的算法来实现。栈的顺序存储结构是：使用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针指示栈顶元素的当前位置。也就是说栈是先进后出的线性表，这样才能判断最近出现括号是否匹配，判断三中括号嵌套使用时是否匹配。

1

沈阳航空航天大学课程设计报告

2 系统设计

2.1 总体方案设计

（1）分析可能不匹配的情况： 1. 首先到来的是右括号。 2. 到来的右括号不是所期待的。 3. 直到程序结束还没到来所期待的括号。 （2）具体分析：

1. 凡出现左括弧，则进栈；

2. 凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配；

3. 表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余。

2.2 数据结构设计

栈的顺序存储结构。

#define SIZE 100 #define ADD 10

typedef struct { char *base,*top; int stacksize; }sqstack;

栈的顺序存储结构是：使用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针指示栈顶元素的当前位置。

2

沈阳航空航天大学课程设计报告

2.3 函数设计

﹙1﹚本系统所设计的函数见表2.1。

表2.1 函数列表

函数名称 main Initstack Push Pop StackEmpty ClearStack DestroyStac k Judge

函数原型 void main()； int Initstack (sqstack &S)； int Push(sqstack &S,char e)； int Pop(sqstack &S,char &e)； int StackEmpty(sqstack &S)； int ClearStack(sqstack &S)； int DestroyStack(sqstack &S)； int Judge(sqstack &S,int &f)； 功能描述 系统主程序 构造一个空栈S 插入元素e为新栈顶 栈顶元素e出栈 判断栈是否为空 把栈重置为空栈 销毁已存在的栈 根据括号出现的情况， 判断是否匹配 ﹙2﹚本系统函数的调用关系见图2.1。

main Initstack Judge ClearStack DestroyStack Push StackEmPop

图2.1 函数调用关系

3

沈阳航空航天大学课程设计报告

2.4 关键流程

2.4.1 系统主流程

（1）主函数的简单描述：

控制程序的结束，调用子函数来实现括号是否匹配的判断。 （2）主函数的流程图。

本函数的具体流程见图2.2。

否

是否继续 初始化建立栈函数 开始 是

是

按键是否出错 判断括号是否匹配函数 否

图2.2 主函数的流程图

结束 销毁栈函数 清空栈函数 4

沈阳航空航天大学课程设计报告

2.4.2 构造一个空栈函数流程

（1）构造一个空栈函数的简单描述：

构造一个空栈，为栈分配存储空间，并对其初始化，使栈顶、栈底指向同一个位子，以便元素进栈。 （2）构造空栈函数的流程图

本函数的具体流程见图2.3。

否 是

图2.3 构造空栈函数的流程图

结束 使栈顶等于栈底 返回出错 栈底是否为空 为栈底分配空间 开始 返回 1 2.4.3 插入元素e为栈顶函数流程

（1）插入元素e为栈顶函数的简单描述：

5

沈阳航空航天大学课程设计报告

让元素e进栈，成为新栈顶，栈顶指针指向下个要进栈的位子，如果栈的储存空间已经满，则为栈追加空间。 （2）插入元素e为栈顶函数的流程图

本函数的具体流程见图2.4。

栈是否已满 开始 是 为栈追加空间 否

栈底是否为空 否 是

元素进栈、栈顶指针移动

图2.4 插入元素e为栈顶函数的流程图

结束 返回 1 使栈顶指针指向要进栈的位子 返回 出错 6

沈阳航空航天大学课程设计报告

2.4.4 栈顶元素e出栈函数流程

（1）栈顶元素e出栈函数的简单描述：

在栈不为空的条件下，栈顶元素出栈，用e带出，调整栈顶指针，使其指向下一个元素进栈的位子。

（2）栈顶元素e出栈函数的流程图

本函数的具体流程见图2.5。

栈是否为空 开始 是 否

返回出错

图2.5 栈顶元素e出栈函数的流程图

结束 返回 1 调整栈顶指针 栈顶元素e出栈 7

沈阳航空航天大学课程设计报告

2.4.5判断栈是否为空函数

（1）判断栈是否为空函数描述：

对已经存在的栈，进行是否为空栈的判断。 （2）判断栈是否为空函数的流程图。

本函数的具体流程见图2.6

开始

栈顶是否等于栈底 否

是

返回1 返回 0

结束

图2.6判断栈是否为空函数流程图

2.4.6把栈重置为空函数

（1）把栈重置为空函数描述：

在完成一次判断以后，使栈顶重新指向栈底，重新把栈置为空栈，以便下次继续进栈，继续判断。

（2）把栈重置为空函数的流程图。

8

沈阳航空航天大学课程设计报告

本函数的具体流程图见图2.7。

栈是否为空 开始 否 是

图2.7把栈重置为空函数流程图

结束 返回 1 栈顶指向栈底 2.4.7销毁已存在的栈函数

（1）销毁已存在的栈函数描述：

对已存在的栈进行对其释放空间，使其销毁。 （2）销毁已存在栈函数的流程图。

本函数的具体流程图见图2.8。

9

沈阳航空航天大学课程设计报告

栈 是 否 存 否 是

图2.8销毁已存在栈函数流程图

结束 返回 1 释放栈的空间 返回 0 在 开始

2.4.8根据括号出现的情况，判断是否匹配函数

（1）根据括号出现的情况，判断是否匹配函数描述：

对出现的括号情况进行判断，如果是 {、[、( 则元素进栈，如果是 }、]、) 则与出栈元素进行比较。匹配继续度字符串，直到读完。如果不匹配则标示，最后输出结果。

（2）根据括号出现的情况，判断是否匹配函数的流程图。

本函数的具体流程图见图2.9。

10

沈阳航空航天大学课程设计报告

否 字符串没结束，匹配标示

是

判断括号 { ) [ ( } ]

是 是否匹配 否

图2.9判断括号匹配函数流程图

结束 返回 1 输出结果 括号进栈 与出栈元素比较 输入字符串 开始 11

沈阳航空航天大学课程设计报告

3 调试分析

(1) 问题1

 问题描述：在字符串最前面多一个右括号时，无法判断是否匹配，输出

的结果仍是匹配。

 问题分析：因为是第一个出现右括号，栈中还没元素，无法出栈，所以

就继续判断后面的，如果后面匹配，则输出匹配。

 解决方法：加一个标识符f，开始赋值为1，如果出现上述情况，则标

识符f改为0，最后根据标识符的值输出是否匹配。 (2) 问题2

 问题描述：在实现循环判断括号匹配情况时，有时不能正确判断。如：

‘ [ ] [ ] [ ’不匹配，再输‘ [ ] [ ] ’还是不匹配。

 问题分析：在判断第一次时到最后一个括号已经进栈，输出结果。再第

二次判断时栈已经有元素，所以不准确。

 解决方法：加一个清空栈的函数，在每次判断之后，都把栈清空，以确

保判断的准确性。 (3) 问题3

 问题描述：如果输入的字符串中括号太多就会出现程序运行出错，会停

止运作。

 问题分析：由于运用的是栈的顺序存储，如果分配空间少，而输入有太

多，就会出现栈溢出。

 解决方法：开始为栈分配空间大些，如果栈要满，追加空间。

12

沈阳航空航天大学课程设计报告

4 测试及运行结果

（1） 主函数的具体的测试结果如图4.1所示。

图4.1 主函数测试结果

（2） 判断是否匹配的具体的测试结果如图4.2所示。

图4.2 判断是否匹配测试结果

13

沈阳航空航天大学课程设计报告

（3）判断结果及循环的具体的测试结果如图4.3所示。

图4.3 判断结果及循环测试结果

（4）循环判断的具体的测试结果如图4.4所示。

14

沈阳航空航天大学课程设计报告

图4.4 循环判断测试结果

（5）退出的具体的测试结果如图4.5所示。

15

沈阳航空航天大学课程设计报告

图4.5退出测试结果

16

沈阳航空航天大学课程设计报告

参考文献

[1] 张长海.C语言程序设计[M].北京:高等教育出版社,2006 [2] 谭浩强.C语言程序设计.北京:清华大学出版社，2005

[3] 严蔚敏 吴伟民.数据结构（C语言版）.北京:清华大学出版社，2007 [4] 王晓东.算法设计与分析[M].北京:清华大学出版社，2007

17

沈阳航空航天大学课程设计报告

附 录

源程序清单：

#include \"stdafx.h\" #include \"stdio.h\" #include \"stdlib.h\" #define SIZE 100 #define ADD 30 #define N 100 typedef struct {

char *base,*top; int stacksize;

}sqstack;

int Initstack (sqstack &S);//构造一个空栈S int Push(sqstack &S,char e);//插入元素e为新栈顶 int Pop(sqstack &S,char &e);//栈顶元素e出栈 int StackEmpty(sqstack &S);//判断栈是否为空 int ClearStack(sqstack &S);//把栈重置为空栈 int DestroyStack(sqstack &S);//销毁已存在的栈

int Judge(sqstack &S,int &f);//根据括号出现的情况，判断是否匹配 void main(int argc, char* argv[]) {

system(\"color f9\"); sqstack S1; int f,k=1; Initstack (S1);

18

沈阳航空航天大学课程设计报告

r: }

int Initstack (sqstack &S)//构造一个空栈S { }

int Push(sqstack &S,char e)//插入元素e为新栈顶 {

if(S.top-S.base>=S.stacksize)//栈满，追加储存空间 {

19

while(k) { }

printf(\"\\n\\n\\*************黄越*************\\n\\n\"); DestroyStack(S1);

f=1; Judge(S1,f);

printf(\"\\n\\如要继续判断，请输入：\\n\"); printf(\"\\退出程序，请按‘0’\"); printf(\"\\n\\\"); scanf(\"%d\system(\"cls\"); if(k!=1&&k!=0)

goto r;

ClearStack(S1);

S.base=(char *)malloc(SIZE*sizeof(char)); if(!S.base)

exit(0);

S.top=S.base; S.stacksize=SIZE; return 1;

沈阳航空航天大学课程设计报告

}

int Pop(sqstack &S,char &e)//栈顶元素e出栈 { }

int StackEmpty(sqstack &S)//判断栈是否为空 { }

int ClearStack(sqstack &S)//把栈重置为空栈 { }

int DestroyStack(sqstack &S)//销毁已存在的栈

20

}

S.base=((char *)realloc(S.base,(S.stacksize+ADD)*sizeof(char))); if(!S.base)

exit(0);

S.top=S.base+S.stacksize; S.stacksize+=ADD;

*S.top++=e; return 1;

if(S.top==S.base)

return 0;

e=*(--S.top); return 1;

if(S.base==S.top)

return 1;

else return 0;

if(S.top!=S.base)

S.top=S.base;

return 1;

沈阳航空航天大学课程设计报告

{ }

int Judge(sqstack &S,int &f)//根据括号出现的情况，判断是否匹配 {

char e,a[N]; int i=0;

printf(\"\\n\\n\\n\\n\\输入要判断的字符串：\\n\"); printf(\"\\n\\\"); scanf(\"%s\getchar();

for(i=0;a[i]!='\\0'&&f;i++) {

f=1; switch(a[i]) { case '{': case '[':

case '(':Push(S,a[i]);break;//出现左括号，进栈 case '}':

if(!StackEmpty(S)) { }

else f=0; break;

21

free(S.base); S.stacksize=0; return 1;

Pop(S,e); if(e!='{')

f=0;

沈阳航空航天大学课程设计报告

}

}

if(!StackEmpty(S))

f=0; case ']':

if(!StackEmpty(S)) { }

else f=0; break;

Pop(S,e); if(e!='[')

f=0;

case ')':

if(!StackEmpty(S)) { }

else f=0; break;

Pop(S,e); if(e!='(')

f=0;

}//出现右括号，若栈不为空，与栈顶元素比较

if(f!=0)

printf(\"\\n\\括号匹配！\\n\");

else printf(\"\\n\\括号不匹配！\\n\"); return 1;

22

沈阳航空航天大学课程设计报告

课程设计总结： 这次课设我抽到题目是：自动括号匹配器的设计。对于判断括号是否匹配算法应借助栈的算法实现。栈是一种运算受的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是栈须遵循“先进后出”的规则，对栈的操作只能在栈顶进行。在这次课设中实现的栈的操作有：构造一个空栈；新元素进栈；栈顶元素出栈；判断栈是否为空；把栈重置为空；销毁已纯在的栈。而括号匹配判断就是通过这些栈的操作实现的。 在这次数据结构课设中遇到了很多实际行的问题，在实际设计中才发现，书上的理论性的东西与在实际运用中的还是有些出入的。所以有些问题不断更正以前错误的思维。通过这次课设我懂得了学习的重要性，了解了理论知识与实践相结合的重要意义。学会了坚持、耐心和努力，这将为以后的学习、工作提供榜样。我觉得作为计算机科学与技术专业的学生来说，这次课设是很有意义的。最重要的是如何把自己平时所学到的知识运用到实际中。虽然自己对这门课程懂的不是很多，很多基础的东西还没有掌握，但是凭借着这段时间的学习，也能够自己把程序弄好，使我渐渐的对这门课程产生了兴趣。 这次课设不仅培养我们思考问题的能力，更提高我们实际操作的水平，增加了对自己对学好这个专业的信心。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩 23