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

Z时代
2024-01-10
分类：综合

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个分组的子表达式，如果它经匹配。否则指的是八进制字符码的表达式。