数据结构练习题之栈与队列:括号匹配问题(C语言实现) 这只是其中一个例题,看完我对这道题的分析之后,关于括号匹配的问题你肯定能够掌握个差不多。转载请注明本文链接! 目录 一、问题描述 二、问题分析 三、代码实现 (一)、定义结构体 (二)、初始化栈 (三)、进栈函数 (四)、判断栈是否为空 (五)、出栈函数 (六)、栈顶素 (七)、主函数 (八)、运行结果 四、完整代码 一、问题描述 Description 给你一串字符,不超过50个字符,可能包括括号、数字、字母、标点符号、空格,你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。 Input 输入数据有多组,处理到文件结束。 Output 如果匹配就输出“yes”,不匹配输出“no” Sample Input (输入) sin(20+10) {[}] Output(输出) yes no 二、问题分析 这是一道让我做了三天才做出来的题,只能说我太,把简单的问题想的过于复杂了。那我们来分析一下括号匹配问题我们需要做什么,我们需要注意什么。 (1)、首先看到括号匹配问题,我们需要一个栈,这个栈是用来存储算术表达式中的左括号'(‘,'{‘,'[‘的。 (2)、在存储左括号时,我们需要判断一下栈是否已满,只要栈不满我们就可以把它直接压入到栈中。 (3)、当我们遇到右括号时,我们需要看一下当前栈中是否有素,如果栈是空的,那么我们就不用判断下去了,直接结束程序,括号是不匹配的;如果栈中有素,那我们我们就拿出来栈顶素,与当前我们遇到的右括号进行匹配,如果他们是一对,那么我们就把当前栈中的左括号出栈,继续扫描算术表达式,循环执行第(2)个步骤和第(3)个步骤;如果不是一对,那么我们也不用继续下去了,直接结束程序,括号是不匹配的。 (4)、我们要知道括号是成对出现的,有左括号无右括号,有右括号无左括号,这都是不行的。需要注意的是:当我们判断括号是否匹配时,不能把栈顶的括号和当前的右括号是否相等作为判断条件。因为左括号和右括号肯定是不相等的。我们只能判断一下当前右括号是哪一种括号,然后我们手动的定义出它对应的左括号,用这个我们定义的左括号和栈顶括号进行是否相等的判断。 (5)、对于这道题来说,当我们遇到’0’时才停止扫描,之所以是‘0’,是因为数组存储完毕后,系统会自动的在末尾加上’0’用来标记数组存储到这里就结束了。否则一直扫描算数表达式中的括号。 (6)、扫描完算术表达式之后,我们要看一下当前栈中是否还有素,如果没有素了,说明括号匹配,如果栈中还有素,说明不匹配。因为我们遇到匹配的括号就执行出栈操作,全部匹配的话,到最后栈中的素应该是都栈了的。 三、代码实现 (一)、定义结构体 根据我们对栈的了解,我们要先定义一个结构体,这个结构体中有一个数组用于存储素,还有一个栈顶标记位top。因为栈是后进先出的。我们只需要一个栈顶标记位就可以对这个栈进行进栈出栈判空等的操作。如果对栈的只是不够熟悉,请先看完有关栈的知识再接着往下看。 (二)、初始化栈 因为数组的下标是从0开始的,刚开始我们并没有存素,那我们让top==-1即可。当存入素的时候,让top+1,然后在它标记的位置存储素即可。 (三)、进栈函数 (四)、判断栈是否为空 (五)、出栈函数 出栈的时候只需判断栈是否为空,如果不为空,那就让栈顶标记位top-1即可。 (六)、栈顶素 当我们遇到右括号的时候,我们就需要栈顶的素了,来判断栈顶素是否和当前右括号匹配。 (七)、主函数 我们上面定义的函数都很简单,主要是看我们在主函数中如何去调用上面这些函数,在什么情况下我们才能用到上面的函数。 (八)、运行结果
四、完整代码 总结:括号匹配问题比较经典,它完美的考察了我们对栈的理解,熟悉栈的操作是基本的,只有把它结合到具体的问题上加以运用才是真的掌握。理论联系实际,实践是检验真理的唯一标准。继续加油。
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/51683.html