括号匹配实验报告

《括号匹配实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称：数据结构班级：实验成绩：实验名称：栈、队列、字符串和数组学号：批阅教师签字：实验编号：实验二姓名：实验日期：指导教师：组号：实验时间：一、实验目的（1）掌握栈、队列、串和数组的抽象数据类型的特征。（2）掌握栈、队列、串和数组的抽象数据类型在计算机中的实现方法。（3）学会使用栈、队列来解决一些实际的应用问题。二、实验内容与实验步骤（1）实验内容：假设表达式中除了变量名、常量和运算符外，还可以允许两种括号：圆括号和中括号，其嵌套的次序随意，编写程序检验输入的表达式中括号的的顺序是否合法。（2）描述抽象数据类型或设计的函

2、数描述，说明为什么要使用这种抽象数据类型，并说明解决设想。抽象数据类型或函数描述：首先定义了一个结构体并且声明为栈类型，在其中定义了空间基地址的指针、栈顶指针以及栈存储空间的大小。之后设计了Creat_Stack的函数，用此函数来创建一个空栈，这样可以使用堆栈来实现括号匹配的功能，又设计了一个名为Stack_Full的函数了来判断栈是否已满，若栈未满才可继续之后的压栈功能，如果堆栈已满，则需要使用realloc来动态分配空间，扩大栈的存储空间。我还设计了一个名为empty的函数，用它来判断堆栈是否为空，堆栈为空或不为空时分别返回0或

3、1。之后设计了名为push和pop的函数来实现括号的入栈和出栈，之后设计了名为Match的函数，来判断括号是否匹配，设计了名为clean的函数来清空堆栈，这样可以连续判断不同的多项式的括号是否匹配。解决设想：对于本题，首先我使用了栈结构，利用栈中数据“先进后出”的特点来实现对括号是否匹配的检验。实现过程基本如下：从左到右依次扫描多项式，如果遇到左括号便将左括号入栈，在所有左括号入栈之后便可以扫描到右括号，如果扫描到的右括号和栈顶的左括号可以匹配时，将左括号出栈，以此类推，最后判断栈是否为空，若为空，则括号匹配，否则括号不匹配。三、实

4、验环境操作系统：Windows7调试软件名称：VC++版本号：6.0上机地点：综合楼311四、实验过程与分析（1）实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。主要函数或操作内部的主要算法：typedefstruct//栈的声明{char*base;//指示存储数据元素的空间基地址的指针char*top;//栈顶指针intstacksize;//栈存储空间大小，以数据元素为单位}SStack;voidCreat_Stack(SStack*s)//创建空栈5{s->base=(char*)m

5、alloc(sizeof(char)*size);if(s->base==NULL)printf("error");else{s->top=s->base;s->stacksize=size;}}上面的算法用来建立栈，该算法的时间复杂度为O(1)，空间复杂度为O（n）。intStack_Full(SStack*s)//判断栈是否为满{if(s->top-s->base>=100)return1;elsereturn0;}intempty(SStack*s)//判断栈是否为空{if(s->base==s->top)return0;

6、elsereturn1;}上面的算法分别用来判断栈是否已满，栈是否为空栈，上面两个算法的时间复杂度和空间复杂度均为O（1）。voidpush(SStack*s,char*str)//入栈{if(Stack_Full(s)!=0){printf("full");}else*s->top++=*str;}voidpop(SStack*s,char*str)//出栈{if(s->base==s->top)printf("Thestackisempty");else*str=*--s->top;}上面两个算法用来实现数据的入栈和出栈

7、，时空复杂度均为O（1）。voidMatch(SStack*s,char*str){inti,j;chart;j=strlen(str);for(i=0;i

8、

9、str[i]=='[')5push(s,str);}for(i=0;itop=='('){pop(s,&t);}elses->top=s->top-1;}if(str[i]==']'){if(*s->top=='['){pop(s,&t);}elses->top=s->t

10、op-1;}}if(empty(s)==0)printf("括号匹配!");elseprintf("括号不匹配!");}该Match函数的作用即判断括号是否匹配，是本程序的核心函数，若假设输入的表达式的长度为n，则此函数中进行