Python实现括号匹配方法详解
这篇文章主要介绍了python实现括号匹配方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)
#-*-coding:utf8-*- #符号表 SYMBOLS={'}':'{',']':'[',')':'(','>':'<'} SYMBOLS_L,SYMBOLS_R=SYMBOLS.values(),SYMBOLS.keys() defcheck(s): arr=[] forcins: ifcinSYMBOLS_L: #左符号入栈 arr.append(c) elifcinSYMBOLS_R: #右符号要么出栈,要么匹配失败 ifarrandarr[-1]==SYMBOLS[c]: arr.pop() else: returnFalse returnTrue print(check("3*{3+[(2-3)*(4+5)]}")) print(check("3*{3+[4-6}]"))
2.
#存储左括号和右括号 open_brackets='([{<' close_brackets=')]}>' #映射左右括号便于出栈判断 brackets_map={')':'(',']':'[','}':'{','>':'<'} #对于每一行数据,进行如下判定若括号为左括号,加入栈,若括号为右括号,判断是否跟栈尾括号对应, 若对应,弹出栈尾元素,若所有括号均正确闭合,则最后栈为空。 forrowinrows: stack=[] label=True forcharinrow: ifcharinopen_brackets: stack.append(char) elifcharinclose_brackets: iflen(stack)<1: label=False break elifbrackets_map[char]==stack[-1]: stack.pop() else: label=False break else: continue ifstack!=[]: label=False print(label) rows=[ '([<^>x[]{a}]{/}{t}g<^>)<{x}b>{x}[b][c[c]]{ {h}}', '[/]{((x)({{*}*}w)w){f}{v}[%(^[z]{u}{})([[]-]h)]{c}(*)[y]}', '<<(^)z>>[b]<>[[(c)u[v]{z>}]g][/b[(])v(v)(+)](v)', '[[b]][(v)g] ([{{<->+}e}[*]d<+>]g[[a]<+>(v){b} ]){a}[u]']
3.
在长度很大的时候可以尽快判断一些比较明显的错误的模式,节省时间:
主要的思路:
首先设置两个列表分别存放的是各种括号的开括号和闭括号,然后遍历给定的字符串,分如下几种情况:
1.字符串首字符出现在闭括号列表中,直接结束,输出错误
2.字符串长度不为偶数,直接结束,输出错误
3.对原始字符串列表化去重,如果去重后的列表长度不为偶数直接结束,输出错误
4.遍历字符串,将属于开括号集合的括号加入到列表中,当遇上一个闭括号的时候计算该闭括号在闭括号列表中的索引与
当前列表最后一个开括号在开括号列表中的索引是否一致,一致则继续,否则直接结束,输出错误
#!usr/bin/envpython #encoding:utf-8 defbracket_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)foroneinset_list] ifone_str[0]inclose_bracket_list: returnFalse eliflength%2!=0: returnFalse eliflen(set_list)%2!=0: returnFalse else: foriinrange(length): ifone_str[i]inopen_bracket_list: tmp_list.append(one_str[i]) elifone_str[i]inclose_bracket_list: ifclose_bracket_list.index(one_str[i])==open_bracket_list.index(tmp_list[-1]): tmp_list.pop() else: returnFalse break returnTrue if__name__=='__main__': one_str_list=['({})','({[<《》>]})','[(]){}','{{{{{{','([{}])','}{[()]'] forone_strinone_str_list: ifbracket_mathch(one_str): print(one_str,'正确') else: print(one_str,'错误') tmp='{}[{()()[]<{{[[[[(())()()(){}[]{}[]()<>]]]]}}>}]' print(bracket_mathch(tmp))
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。