python实现括号匹配的思路详解

2024-03-27 21:51:01

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}]"))

# 存储左括号和右括号
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]']

在长度很大的时候可以尽快判断一些比较明显的错误的模式，节省时间:

主要的思路：

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

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))

PS：下面看下python 匹配格式

匹配格式

模式	描述
^	匹配字符串的开头
$	匹配字符串的末尾。
.	匹配任意字符，除了换行符，当re.DOTALL标记被指定时，则可以匹配包括换行符的任意字符。
[...]	用来表示一组字符,单独列出：[amk] 匹配 'a'，'m'或'k'
[^...]	不在[]中的字符：[^abc] 匹配除了a,b,c之外的字符。
re*	匹配0个或多个的表达式。
re+	匹配1个或多个的表达式。
re?	匹配0个或1个由前面的正则表达式定义的片段，非贪婪方式
re{ n}
re{ n,}	精确匹配n个前面表达式。
re{ n, m}	匹配 n 到 m 次由前面的正则表达式定义的片段，贪婪方式
a\| b	匹配a或b
(re)	G匹配括号内的表达式，也表示一个组
(?imx)	正则表达式包含三种可选标志：i, m, 或 x 。只影响括号中的区域。
(?-imx)	正则表达式关闭 i, m, 或 x 可选标志。只影响括号中的区域。
(?: re)	类似 (...), 但是不表示一个组
(?imx: re)	在括号中使用i, m, 或 x 可选标志
(?-imx: re)	在括号中不使用i, m, 或 x 可选标志
(?#...)	注释.
(?= re)	前向肯定界定符。如果所含正则表达式，以 ... 表示，在当前位置成功匹配时成功，否则失败。但一旦所含表达式已经尝试，匹配引擎根本没有提高；模式的剩余部分还要尝试界定符的右边。
(?! re)	前向否定界定符。与肯定界定符相反；当所含表达式不能在字符串当前位置匹配时成功
(?> re)	匹配的独立模式，省去回溯。
\w	匹配字母数字
\W	匹配非字母数字
\s	匹配任意空白字符，等价于 [\t\n\r\f].
\S	匹配任意非空字符
\d	匹配任意数字，等价于 [0-9].
\D	匹配任意非数字
\A	匹配字符串开始
\Z	匹配字符串结束，如果是存在换行，只匹配到换行前的结束字符串。c
\z	匹配字符串结束
\G	匹配最后匹配完成的位置。
\b	匹配一个单词边界，也就是指单词和空格间的位置。例如， 'er\b' 可以匹配"never" 中的 'er'，但不能匹配 "verb" 中的 'er'。
\B	匹配非单词边界。'er\B' 能匹配 "verb" 中的 'er'，但不能匹配 "never" 中的 'er'。
\n, \t, 等.	匹配一个换行符。匹配一个制表符。等
\1...\9	匹配第n个分组的子表达式。
\10	匹配第n个分组的子表达式，如果它经匹配。否则指的是八进制字符码的表达式。

总结

以上所述是小编给大家介绍的python实现括号匹配的思路详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

Python实现的括号匹配判断功能示例

本文实例讲述了Python实现的括号匹配判断功能.分享给大家供大家参考,具体如下: 1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys() def check(s): arr = [] for c
Python实现求解括号匹配问题的方法

本文实例讲述了Python实现求解括号匹配问题的方法.分享给大家供大家参考,具体如下: 这个在本科学习数据结构的时候已经接触很多了,主流的思想是借助栈的压入.弹出来进行匹配,至于python的话可以使用列表来完成这个操作,因为列表的append方法相当于栈的push方法,列表的pop方法相当于栈的pop方法. 主要的思路: 首先设置两个列表分别存放的是各种括号的开括号和闭括号,然后遍历给定的字符串,分如下几种情况: 1.字符串首字符出现在闭括号列表中,直接结束,输出错误 2.字符串长度不为偶数,
python使用正则表达式替换匹配成功的组

正则表达式简介正则表达式,又称正规表示式.正规表示法.正规表达式.规则表达式.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE),计算机科学的一个概念.正则表达式使用单个字符串来描述.匹配一系列符合某个句法规则的字符串.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本. 许多程序设计语言都支持利用正则表达式进行字符串操作.例如,在Perl中就内建了一个功能强大的正则表达式引擎.正则表达式这个概念最初是由Unix中的工
Python 匹配任意字符（包括换行符）的正则表达式写法

想使用正则表达式来获取一段文本中的任意字符,写出如下匹配规则: (.*) 结果运行之后才发现,无法获得换行之后的文本.于是查了一下手册,才发现正则表达式中,"."(点符号)匹配的是除了换行符"\n"以外的所有字符. 以下为正确的正则表达式匹配规则: ([\s\S]*) 同时,也可以用 "([\d\D]*)"."([\w\W]*)" 来表示. Web技术之家_www.waweb.cn 在文本文件里, 这个表达式可以匹配所有的英文
python用户评论标签匹配的解决方法

我们观察用户评论发现:属性词往往和情感词伴随出现,原因是用户通常会在描述属性时表达情感,属性是情感表达的对象.还发现:属性词和专用情感词基本都是名词或形容词(形谓词). 算法流程图如下: 评论数据如下: 代码如下: #encoding=utf-8 ############################# # # 功能:给定一些中文的产品评论,希望从中找到评价对象及评价词. # # @author:licl # ############################## fdata = ope
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实现一个栈判断括号是否平衡

栈(Stack)在计算机领域是一个被广泛应用的集合,栈是线性集合,访问都严格地限制在一段,叫做顶(top). 举个例子,栈就想一摞洗干净的盘子,你每次取一个新盘子,都是放在这一摞盘子的最上头,当你往里面添加盘子的时候,也是放在最上面,处在底部的盘子,你可能永远也用不到. 栈的最常见操作,有如下两个: push(a) # 压入,将a压入的栈中 pop() # 弹出,将栈的最后一个元素弹出可是使用Python的列表数据结构,来模拟栈的操作,使用 append 来模拟 push ,使用列表的 pop
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实现括号匹配的思路详解

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.appe
python实现爬山算法的思路详解

问题找图中函数在区间[5,8]的最大值重点思路爬山算法会收敛到局部最优,解决办法是初始值在定义域上随机取乱数100次,总不可能100次都那么倒霉. 实现 import numpy as np import matplotlib.pyplot as plt import math # 搜索步长 DELTA = 0.01 # 定义域x从5到8闭区间 BOUND = [5,8] # 随机取乱数100次 GENERATION = 100 def F(x): return math.sin(x*x)
Python实现仿射密码的思路详解

仿射密码思路: 1.加解密公式: 2.构造对应字典: 3.代码实现构造字典,建立映射关系: # 构造字典,'A' --> 0 ... def char_2_num(x): list_s = [] list_num = [] for i in range(26): c = chr(i + 65) list_s.append(c) list_num.append(i) c_2_n = dict(map(lambda x, y: [x, y], list_s, list_num)) return c
Java 括号匹配问题案例详解

目录前言例题算法思想算法举例代码栈类括号匹配核心算法完整代码运行结果前言括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现.最近刷题的时候也遇到了,就想写一篇文章整理一下. 例题题目来自Leetcode中国给定一个只包括 (,),{,},[,] 的字符串,判断字符串是否有效. 有效字符串需满足: 1.左括号必须用相同类型的右括号闭合. 2.左括号必须以正确的顺序闭合. 注意空字符串可被认为是有效字符串. 示例 1: 输入: "()"
C语言解决堆栈括号匹配问题示例详解

目录首先构建栈调用匹配函数代码调用 1.括号匹配问题就是当遇到{( [这些左括号的时将括号字符入栈 2.当遇到右括号时判断栈顶元素是不是与左括号匹配如果匹配就出栈如果不匹配就直接结束程序(即括号匹配失败) 首先构建栈 struct STACK { char num[10]; int top; }; struct STACK* creatstack() { struct STACK* stack = new struct STACK; assert(stack); stack->top
Python批量裁剪图片的思路详解

目录需求思路程序测试需求我的需求是批量裁剪某一文件夹下的所有图片,并指定裁剪宽高. 思路 1. 先使用PIL.Image.size获取输入图片的宽高.2.宽高除以2得到中心点坐标3.根据指定宽高,以中心点向四周拓展4.调用PIL.Image.crop完成裁剪程序 import os from PIL import Image def crop(input_img_path, output_img_path, crop_w, crop_h): image = Image.open(i
利用Python实现字幕挂载的思路详解

其实超简单超简单!python好现成的库,一下子省略了好多步骤! 本文在Windows环境下!linux只是不需要手动输入imagicmagick的位置! 需要用到的环境 python(基本上只要不是很老的就行) pip(这个其实python版本>2.8.9或者>3.4的都自带了),可以通过cmd命令pip -V查询是否安装了,没有的话就输入命令需要用到的工具: 我用的是pycharm,用来写python代码的. Flie->setting->Project:Test->p
python Opencv实现停车位识别思路详解

目录 1.实现的思路 2.整体代码实战 3.停车位视频下载 1.实现的思路 (1)首先使用一个处理画框的程序,将图片中的有车和无车的停车位给画出来,并且保存坐标(如果画错了,将鼠标移至要删除的框中,右击鼠标,即可删除): #定义回调函数 def mouseClick(events,x,y,flags,params): #按下鼠标左键,将点击的坐标(x,y)保存到position列表中 if (events&cv2.EVENT_LBUTTONDOWN==cv2.EVENT_LBUTTONDOWN)
Python实现括号匹配方法详解

这篇文章主要介绍了python实现括号匹配方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.ke
用Python从0开始实现一个中文拼音输入法的思路详解

众所周知,中文输入法是一个历史悠久的问题,但也实在是个繁琐的活,不知道这是不是网上很少有人分享中文拼音输入法的原因,接着这次NLP Project的机会,我觉得实现一发中文拼音输入法,看看水有多深,结果发现还挺深的,但是基本效果还是能出来的,而且看别的组都做得挺好的,这次就分享一下我们做的结果吧. (注:此文假设读者已经具备一些隐马尔可夫模型的知识) 任务描述实现一个中文拼音输入法. 经过分析,分为以下几个模块来对中文拼音输入法进行实现: 核心功能包括拼音切分(SplitPinyin.py)

python实现括号匹配的思路详解

相关推荐

随机推荐