算法创作|栈的应用——括号匹配问题解决方法

问题描述假设我们有一个复杂的字符串,里边包含了多种括号的嵌套,如下图:

这时候人为地用肉眼去判断其中的括号是否匹配是一件非常麻烦的事,不仅耗时耗力,而且准确率极低。那么,有什么方法可以帮助我们高效地进行判断呢,根据栈的特点,我们可以很容易地想到利用python中的list来模拟栈结构进行判断。示例:输入:((ABCD(x)输出:False输入:{[(rttyy)]sss}输出:True解决方案我们用栈来保存未匹配的左括号,利用for循环从左到右依次遍历字符串的每个元素。当遍历到左括号时,则将其压入栈中;当遍历到右括号时,从栈顶取出一个左括号。如果能够匹配,则继续遍历剩下的字符串。如果遍历的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明该字符串的括号匹配有误,直接返回False。当所有的括号都扫描完成之后,如果栈为空则说明该字符串的括号全部匹配正确,返回True;如果栈不为空,说明有未匹配的左括号,则返回False。# coding:utf-8def BracketMatch(str):#把左括号与右括号分别放在一组LeftBrackets  = '{[('RightBrackets = '}])'#根据括号的匹配关系建立一个字典,右括号当key,左括号当valueBrackets = {'}':'{',']':'[',')':'('}# 建立一个栈,初始值为空列表Stack = [ ]for char in (str):if char in LeftBrackets:Stack.append(char)if char in RightBrackets:if Stack == [ ]:return Falseelse:if Brackets[char] == Stack[-1]:Stack.pop()else:return Falseif Stack == [ ]:return Trueelse:return Falsestr = input('请输入字符:')print(BracketMatch(str))运行结果如下图:

结语此题难度一般,最关键的是要理解栈结构的特点,就是后进先出,了解了栈的特点后再运用遍历和嵌套判断便可解决这个问题。当然,这只是其中一种解决办法,我们只有通过不断地学习才能写出更优的算法和代码。实习编辑:王晓姣作者:唐雷清,祝菱晞,刘紫轩稿件来源:深度学习与文旅应用实验室(DLETA)

(0)

相关推荐

  • 在C 中将String转换为Char数组并将Char数组转换为String

    In this article, we will be focusing on the different ways to convert String to char array and char ...

  • ​LeetCode刷题实战186:翻转字符串里的单词 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 算法创作|找出游戏的获胜者问题解决方法

    问题描述共有 n 名小伙伴一起做游戏.小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号.确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i ...

  • 算法创作|得到的最晚有效时间问题解决方法

    问题描述你一个字符串 time ,格式为 hh:mm(小时:分钟),其中某几位数字被隐藏(用 ? 表示).有效的时间为 00:00 到 23:59 之间的所有时间,包括 00:00 和 23:59 . ...

  • 算法创作|蓝桥杯关于成绩统计问题解决方法

    标题问题描述示例:小蓝给学生们组织了一场考试,卷面总分为 100 分,每个学生的得分都是一个 0 到 100 的整数.如果得分至少是 60 分,则称为及格.如果得分至少为 85 分,则称为优秀.请计算 ...

  • 算法创作|栈相关问题的解决方法

    问题描述 在平时是学习中经常会遇到栈,可栈到底是什么,在生活中有什么应用呢? 解决方案 在数据结构中,栈是保存数据元素的容器,可以把数据存入其中也可取出使用,同样支持访问操作包括查看. 既然它作为一个 ...

  • 算法创作|神奇语言问题解决方法

    问题描述一位同学正在学习一门神奇的语言,其中的单词都是由小写英文字母组成,有些单词很长,而这位同学一直记不住,他准备不再完全记忆这些单词,而是根据单词中哪个字母出现的最多来分辨单词,现在请帮助这位同学 ...

  • 算法创作|阶梯电价问题解决方法

    问题描述为了提倡居民节约用电,某省电力公司执行"阶梯电价",安装一户一表的居民用户电价分为两个"阶梯":月用电量50千瓦时(含50千瓦时)以内的,电价为0.53 ...

  • 算法创作 | 0到n-1中缺失的数字问题解决方法

    问题描述一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0-n-1之内.在范围0-n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字.示例1:输入:[0,1,3 ...

  • 算法创作 | 二叉树遍历问题解决方法

    问题描述二叉树的先序遍历.中序遍历.后序遍历怎么求?解决方案给你一个二叉树(如图)那么怎么找出它的先序遍历.中序遍历.后序遍历呢?我们先看一个简单二叉树来了解它的概念. 所谓前序,中序,后序就是指根所 ...

  • 算法创作|“画雪人”问题解决方法

    问题描述示例:运用Turtle画出一个戴帽子的雪人在你门前,我堆起一个雪人,代表笨拙的我,把你久等...解决方案掌握turtle库,you can do you want.代码清单 1 DFS求解1到 ...