Python实现括号匹配方法详解
作者:xushukui 发布时间:2021-05-01 23:06:58
标签:python,括号,匹配
这篇文章主要介绍了python实现括号匹配方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)
# -*- coding: utf8 -*-
# 符号表
SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'}
SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys()
def check(s):
arr = []
for c in s:
if c in SYMBOLS_L:
# 左符号入栈
arr.append(c)
elif c in SYMBOLS_R:
# 右符号要么出栈,要么匹配失败
if arr and arr[-1] == SYMBOLS[c]:
arr.pop()
else:
return False
return True
print(check("3 * {3 +[(2 -3) * (4+5)]}"))
print(check("3 * {3+ [4 - 6}]"))
2.
# 存储左括号和右括号
open_brackets = '([{<'
close_brackets = ')]}>'
# 映射左右括号便于出栈判断
brackets_map = {')': '(', ']': '[', '}': '{', '>': '<'}
# 对于每一行数据,进行如下判定若括号为左括号,加入栈,若括号为右括号,判断是否跟栈尾括号对应,
若对应,弹出栈尾元素,若所有括号均正确闭合,则最后栈为空。
for row in rows:
stack = []
label = True
for char in row:
if char in open_brackets:
stack.append(char)
elif char in close_brackets:
if len(stack) < 1:
label = False
break
elif brackets_map[char] == stack[-1]:
stack.pop()
else:
label = False
break
else:
continue
if stack != []:
label = False
print(label)
rows = [
'([<^>x[ ]{a}]{/}{t}g<^>)<{x}b>{x}<z({%}w >[b][c[c]]{<h>{h}}',
'[/]{((x)({{*}*}w)w){f}{v}[%(^[z]{u}{ })([[ ]-]h)]{c}(*)[y]}',
'<<(^)z>>[b]< >[[(c)u[v]{z<b< >><b>}]g][/b[(])v(v)(+)](v)',
'[[b]][(v)g]<z>([{{<->+}e}[*]d<+>]g[[a] <+>(v){b}<e>]){a}[u]']
3.
在长度很大的时候可以尽快判断一些比较明显的错误的模式,节省时间:
主要的思路:
首先设置两个列表分别存放的是各种括号的开括号和闭括号,然后遍历给定的字符串,分如下几种情况:
1.字符串 首字符 出现在闭括号列表中,直接结束,输出错误
2.字符串长度不为偶数,直接结束,输出错误
3.对原始字符串列表化去重,如果去重后的列表长度不为偶数直接结束,输出错误
4.遍历字符串,将属于开括号集合的括号加入到列表中,当遇上一个闭括号的时候计算该闭括号在闭括号列表中的索引与
当前列表最后一个开括号在开括号列表中的索引是否一致,一致则继续,否则直接结束,输出错误
#!usr/bin/env python
# encoding:utf-8
def bracket_mathch(one_str):
'''''
括号匹配
'''
tmp_list = []
open_bracket_list = ['(', '[', '{', '<', '《']
close_bracket_list = [')', ']', '}', '>', '》']
one_str_list = list(one_str)
length = len(one_str_list)
set_list = list(set(one_str_list))
num_list = [one_str_list.count(one) for one in set_list]
if one_str[0] in close_bracket_list:
return False
elif length % 2 != 0:
return False
elif len(set_list) % 2 != 0:
return False
else:
for i in range(length):
if one_str[i] in open_bracket_list:
tmp_list.append(one_str[i])
elif one_str[i] in close_bracket_list:
if close_bracket_list.index(one_str[i]) == open_bracket_list.index(tmp_list[-1]):
tmp_list.pop()
else:
return False
break
return True
if __name__ == '__main__':
one_str_list = ['({})', '({[<《》>]})', '[(]){}', '{{{{{{', '([{}])', '}{[()]']
for one_str in one_str_list:
if bracket_mathch(one_str):
print(one_str, '正确')
else:
print(one_str, '错误')
tmp = '{}[{()()[]<{{[[[[(())()()(){}[]{}[]()<>]]]]}}>}]'
print(bracket_mathch(tmp))
来源:https://www.cnblogs.com/nyist-xsk/p/9481427.html
0
投稿
猜你喜欢
- 目录1.随机取小数:2.整数的随机选取:3.随机列表取数,元素打乱:总结1.随机取小数:import randomprint(random.
- 目录什么是websocket?第一步 准备工作第二步 编写聊天室页面第三步 编写后台websocket路由及处理方法第四步 运行看效果小结C
- 安装模块下面需要用模块,先安装一下:pip install numpy pip install opencv-python==4.5.5.6
- 正文开始if name == "main":可以看成是python程序的入口,就像java中的main()方法,但不完全
- 经常会在连接DB的时候用到,就是不知道代表什么意思。。。RS.OPEN SQL,CONN,A,BA: ADOPENFORWARDONLY(=
- 我想做一个页面,10秒后转向其它页。想在网页中显示10秒的倒计时。谢谢了。对JS不懂 方法一:<html><h
- 最近一个项目中遇到ASP对FoxPro库表(*.DBF)的操作问题。现实中确有许多应用软件使
- 最近,小明为了达成小姐姐的愿望,在某宝买到心仪的宝贝,再加上又迷上了python,就通过python轻而易举地实现了(个人声明:对Java来
- 现在很多地方都需要用到关键词过滤功能。比如一般的服务器都不允许一些词出现在网页上,站长有时候会对在本网站发布信息的内容进行一个广告过滤等。雨
- 匹配括号接下来,我们使用栈解决实际的计算机科学问题。比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ (
- <%on error resume nextdim conn,sql,rsset conn=Server.CreateObject(&
- match()函数的使用。以及从文本中提取数据的方法。在学习re模块的相关函数前应了解正则表达式的特殊字符准备一个要爬取的文本文档:直接从某
- 分析数字中经常是3个数字一组,之后跟一个逗号,因此规律为:***,***,***正则式[a-z]+,[a-z]?import resen =
- vbscript脚本中,fso对象CreateTextFile方法调用时可能会报“无效的过程调用或参数”错误,在使用ASP生成静态页面时,如
- 分页的首页<meta http-equiv="Content-Type" content="text/h
- 本文实例讲述了python分支、循环简单用法。分享给大家供大家参考,具体如下:讲程序设计,不得不讲到顺序、分支、循环。顺序就是从上到下运行代
- 本文实例讲述了Python面向对象之私有属性和私有方法。分享给大家供大家参考,具体如下:01. 应用场景及定义方式应用场景在实际开发中,对象
- 因项目需要根据指定格式的文件生成XML标注文件,可以方便使用LabelImg打开进行编辑和查看。其原始文件默认使用逗号进行分隔,如下
- 1. 前言熟悉 Django 的朋友应该知道,我们可以通过「 inspectdb 」命令将数据库表反向生成 Model 并写入到文件中去比如
- 项目说明开发php项目管理系统,由于是新项目且已经部署在生产环境,导致需要根据实际使用情况,进行及时的功能升级或bug修复。每次升级,进行程