Python实现求解括号匹配问题的方法

本文实例讲述了Python实现求解括号匹配问题的方法。分享给大家供大家参考，具体如下：

这个在本科学习数据结构的时候已经接触很多了，主流的思想是借助栈的压入、弹出来进行匹配，至于python的话可以使用列表来完成这个操作，因为列表的append方法相当于栈的push方法，列表的pop方法相当于栈的pop方法。

主要的思路：

首先设置两个列表分别存放的是各种括号的开括号和闭括号，然后遍历给定的字符串，分如下几种情况：

1.字符串首字符出现在闭括号列表中，直接结束，输出错误

2.字符串长度不为偶数，直接结束，输出错误

3.对原始字符串列表化去重，如果去重后的列表长度不为偶数直接结束，输出错误

4.遍历字符串，将属于开括号集合的括号加入到列表中，当遇上一个闭括号的时候计算该闭括号在闭括号列表中的索引与当前列表最后一个开括号在开括号列表中的索引是否一致，一致则继续，否则直接结束，输出错误

主要是在长度很大的时候可以尽快判断一些比较明显的错误的模式，节省时间，按照这个简单的思想，下面是具体的实现：

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：括号匹配的相关问题
'''
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)

结果如下：

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:

  • python正则表达式中的括号匹配问题
  • Python正则表达式实现截取成对括号的方法
  • Python做简单的字符串匹配详解
  • Python利用正则表达式匹配并截取指定子串及去重的方法
  • python使用正则表达式匹配字符串开头并打印示例
  • Python正则表达式匹配中文用法示例
  • python通过BF算法实现关键词匹配的方法
  • Python正则表达式非贪婪、多行匹配功能示例
  • Python算法之栈（stack）的实现
  • python实现堆栈与队列的方法
  • 栈和队列数据结构的基本概念及其相关的Python实现
赞 (0)

相关推荐

  • python正则表达式中的括号匹配问题

    问题: m = re.findall('[0-9]*4[0-9]*', '[4]') 可以匹配到4. m = re.findall('([0-9])*4([0-9])*', '[4]') 匹配不到4. 这是为什么呢?PS,这个是一个简化的说明,我要用的正则比这个复杂,所以要用到(),表示一个序列的匹配. 补充一点,我放在notepad++中用的时候,两种写法都能匹配出来,不知道为什么python中就不行了. 答案: python的正则中用()会进行匹配,所以返回结果是['',''],就是两个()

  • Python正则表达式非贪婪、多行匹配功能示例

    本文实例讲述了Python正则表达式非贪婪.多行匹配功能.分享给大家供大家参考,具体如下: 一些regular的tips: 1 非贪婪flag >>> re.findall(r"a(\d+?)","a23b") # 非贪婪模式 ['2'] >>> re.findall(r"a(\d+)","a23b") ['23'] 注意比较这种情况: >>> re.findall(r&q

  • Python正则表达式实现截取成对括号的方法

    本文实例讲述了Python正则表达式实现截取成对括号的方法.分享给大家供大家参考,具体如下: strs = '1(2(3(4(5(67)6)7)8)9)0' reg1 = re.compile('([()])∗') #一对括号 reg2 = re.compile('([()]|\([()]∗)*\)') #两对括号 reg3 = re.compile('([()]|\([()]∗|([()]|\([()]∗)*\))*\)') #三层 函数 #匹配成对括号正则表达式 def getReg(sel

  • Python利用正则表达式匹配并截取指定子串及去重的方法

    本文实例讲述了Python利用正则表达式匹配并截取指定子串及去重的方法.分享给大家供大家参考.具体如下: import re pattern=re.compile(r'\| (\d+) \| (\d+) \|') numset=set() all=''' | 29266795 | 533 | | 29370116 | 533 | | 29467495 | 533 | | 29500404 | 533 | | 29500622 | 533 | | 29515964 | 530 | | 295160

  • 栈和队列数据结构的基本概念及其相关的Python实现

    先来回顾一下栈和队列的基本概念: 相同点:从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同. 不同点:栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表. 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表.它们是完全不同的数据类型.除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定". 栈必须按"后进先出"的规则进行操作:比如说,小学老师批改学生的作业,如果不打乱作业本的顺

  • Python正则表达式匹配中文用法示例

    Python正则表达式匹配中文用法示例

    本文实例讲述了Python正则表达式匹配中文用法.分享给大家供大家参考,具体如下: #!/usr/bin/python #-*- coding:cp936-*-#思路,将str转换成unicode,方可用正则表达式,前提是,要知道文件的编码,本例中是gbk import cPickle as mypickle import re import sys if (__name__=='__main__'): fid1=file('demo.txt','r');#demo.txt写入字符如:我们 p=

  • python通过BF算法实现关键词匹配的方法

    本文实例讲述了python通过BF算法实现关键词匹配的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: #!/usr/bin/python # -*- coding: UTF-8 # filename BF import time """ t="this is a big apple,this is a big apple,this is a big apple,this is a big apple." p="apple&q

  • python使用正则表达式匹配字符串开头并打印示例

    本文实例讲述了python使用正则表达式匹配字符串开头并打印的方法.分享给大家供大家参考,具体如下: import re s="name=z1hangshan username=fff url=www.baidu.com password=ddd256" s2="username=fff name=z1hangshan url=www.baidu.com password=ddd256" #p=re.compile(r'((?:\s)name=(\S)+)') p=

  • Python算法之栈（stack）的实现

    本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价值.具体内容如下: 1.栈stack通常的操作: Stack() 建立一个空的栈对象 push() 把一个元素添加到栈的最顶层 pop() 删除栈最顶层的元素,并返回这个元素 peek()  返回最顶层的元素,并不删除它 isEmpty()  判断栈是否为空 size()  返回栈中元素的个数 2.简单案例以及操作结果: Stack Operation Stack Contents Return

  • python实现堆栈与队列的方法

    本文实例讲述了python实现堆栈与队列的方法.分享给大家供大家参考.具体分析如下: 1.python实现堆栈,可先将Stack类写入文件stack.py,在其它程序文件中使用from stack import Stack,然后就可以使用堆栈了. stack.py的程序: 复制代码 代码如下: class Stack():      def __init__(self,size):          self.size=size;          self.stack=[];         

  • Python做简单的字符串匹配详解

    Python做简单的字符串匹配详解 由于需要在半结构化的文本数据中提取一些特定格式的字段.数据辅助挖掘分析工作,以往都是使用Matlab工具进行结构化数据处理的建模,matlab擅长矩阵处理.结构化数据的计算,Python具有与matlab共同的特点:语法简洁.库丰富,对算法仿真来说都是一门简洁易用的语言. Python做字符串匹配相对来说上手比较容易,且具有成熟的字符串处理库re供我们使用: 在re库的帮助下,只需简单的两步就可完成匹配工作,对做数据分析/算法的工作者来说,轻松了许多: ste

随机推荐