括号匹配的原理_数据结构与算法题库

栈的应用（括号匹配算法实战）　　一、实验内容　　      1.实验目的　　栈（Stack）是线性结构的核心内容之一。本实验要求用高级语言C语言编写基于栈的顺序存储结构实现栈的入栈、出栈、取栈顶素和判空操作，并基于上述栈的基本操作实现括号匹配算法，完成实验报告的填写，以便加深理解有关栈结构的抽象数据类型等概念，并体会和了解栈结构在日常用户输入操作中的应用价值。　　      2.实验内容　　       1) 构建一个栈的顺序存储结构的抽象数据类型，通常应包含如下步骤：　　            a.定义用来描述顺序栈结构的结构体变量类型SqStack；　　            b.编写一个顺序栈初始化算法，记为InitStack操作（函数）；　　            c.编写一个顺序栈数据素入栈算法，记为push操作（函数）；　　            d.编写一个顺序栈数据素出栈算法，记为pop操作（函数）；　　            e.编写一个取栈顶素算法，记为GetTop操作（函数）；　　            f.编写一个判空算法，记为IsEmpty操作（函数）；　　      2）基于上述栈的基本操作实现括号匹配算法：　　            a.在main函数内部编写一个括号匹配算法，要求从键盘上输入一个　　表达式，判断这个表达式中的括号是否匹配；　　            b.测试实验结果，评估实验过程. 　　      3）完成实验报告的填写　　     顺序栈结构的逻辑结构原理如下：　　
　　栈结构的逻辑结构　　      括号匹配的逻辑结构原理如下：　　
　　括号匹配的逻辑结构　　      利用栈结构后进先出的有限操作特点，通过入栈和出栈的操作来实现对表达式括号匹配正确与否的判断. 　　二、实验过程　　1.顺序栈结构体定义　　       首先用C/C++开发环境新建源文件，首先键入如下预定义命令行：　　
　　图1 源文件预定义命令行　　    注意这里需要#include命令行引用string.h头文件，因为该文件里包含后面操作所需要的strlen库函数，用于字符串的长度。　　      接着，根据顺序栈的逻辑结构原理图，定义用来描述顺序栈数据对象的结构体变量类型SqStack，代码如下：　　
　　图2顺序栈的结构体类型定义　　      这里用char作为顺序栈数据素的数据类型，得到SqStack（顺序栈结构体变量）的定义。其中用base表示栈底指针，用top表示栈顶指针，用stackSize表示当前栈的大小（即顺序栈中数据素的个数）。　　2. InitStack函数　　       编写顺序栈的初始化操作,首先对传入的SqStack型参数分配初始大小的存储空间，这里用100个char的大小来初始化顺序栈，如果内存分配失败则退出程序，否则将S.base赋给S.top，STACK_INIT_SIZE赋给S.stackSize。　　      代码如下：　　
　　图3 InitStack函数　　3. IsEmpty函数　　       判空操作：如果栈底指针与栈顶指针相等，则顺序栈为空，反之非空。栈是否为空是字符串序列中括号是否匹配的判断依据。　　
　　图4 IsEmpty函数　　4. push、pop和GetTop函数　　
　　图 5 push函数　　　　      push函数实现入栈操作，如果栈已满，则动态增加顺序栈的内存，将传入的参数e赋给当前栈顶指针所指向的栈内素，赋值结束后栈顶指针自动上移（自加）。　　
　　图 6 GetTop函数　　    GetTop函数实现取栈顶素操作，如果栈为空，则操作失败，否则将栈顶指针的下一位指针所指向的数据素赋给参数e，赋值结束返回e。　　
　　图 7 pop函数　　    pop函数实现出栈操作，如果为空，则操作失败，将栈顶指针的下一位指针所指向的数据素赋给参数e，赋值结束后栈顶指针自动下移（自减）。　　　　5.括号匹配算法的实现　　
　　图8 括号匹配算法　　       1. 声明一个大小为MAXSIZE（宏定义）的char型数组，并初始化；　　      2. 声明两个char型变量m，n；　　      3. 用char型数组a来接收从用户界面输入的字符串序列，getchar用于消化最后一次ENTER键字符输入；　　      4. length表示字符串的长度；　　      5. 声明一个SqStack类型变量并初始化；　　      6. 用for循环来实现括号匹配的迭代过程，如果迭代获得的当前字符为（、{、[就调用push函数将字符压入顺序栈中，如果迭代获得的当前字符为）、}、]就调用GetTop函数取栈顶素判断是否与当前字符相等，如果相等则实现出栈操作，如果不相等则输出“括号不匹配”并返回0退出程序；　　      7. 如果在for循环中没有意外退出程序的前提下，继续进行判空操作，如果顺序栈为空，则括号匹配，反之不匹配; 　　      8. 编译运行，测试代码. 　　三、实验结果　　
　　
　　图9 实验结果　　　　       实验结果与预期目标一致，能够正确预测字符串序列是否括号匹配。　　四、实验总结　　       通过“栈的应用”这个实验，深入了解到采用栈结构处理日常生活中的用户操作无处不在，在实现括号匹配算法的过程中，主要利用栈结构后进先出的特性以及栈的入栈、出栈、取栈顶素和判空操作来实现。其次从键盘上输入一个字符串表达式，判断这个表达式中的括号是否匹配来测试代码的正确性。　　在实验的过程中，体会到了栈结构的顺序存储方式的优点，就本实验而言，由于输入的表达式数据量不是特别大，顺序结构满足算法的实现。同时节省了一些存储空间的开销。　　       栈结构不仅仅可以用来处理括号匹配的判断问题，还可以实现函数的递归调用，使得程序的运行有确定的入口和出口，为高效地算法实现提供了基础。　　总的来说加深理解有关栈结构的抽象数据类型等概念，并体会和了解栈结构在日常用户输入操作中的应用价值。

括号匹配的原理_数据结构与算法题库

相关推荐