python實現(xiàn)括號匹配的思路詳解

更新時間：2018年08月23日 11:30:33 作者：xushukui

這篇文章主要介紹了python實現(xiàn)括號匹配及匹配格式的相關(guān)知識，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下

1.用一個?！緋ython中可以用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 = {')': '(', ']': '[', '}': '{', '>': '<'}
# 對于每一行數(shù)據(jù)，進行如下判定若括號為左括號，加入棧，若括號為右括號，判斷是否跟棧尾括號對應(yīng)，
 若對應(yīng)，彈出棧尾元素，若所有括號均正確閉合，則最后棧為空。
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)<e>]){a}[u]']

在長度很大的時候可以盡快判斷一些比較明顯的錯誤的模式，節(jié)省時間:

主要的思路：

首先設(shè)置兩個列表分別存放的是各種括號的開括號和閉括號，然后遍歷給定的字符串，分如下幾種情況：

1.字符串首字符出現(xiàn)在閉括號列表中，直接結(jié)束，輸出錯誤
2.字符串長度不為偶數(shù)，直接結(jié)束，輸出錯誤
3.對原始字符串列表化去重，如果去重后的列表長度不為偶數(shù)直接結(jié)束，輸出錯誤
4.遍歷字符串，將屬于開括號集合的括號加入到列表中，當遇上一個閉括號的時候計算該閉括號在閉括號列表中的索引與

當前列表最后一個開括號在開括號列表中的索引是否一致，一致則繼續(xù)，否則直接結(jié)束，輸出錯誤

#!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匹配括號內(nèi)的表達式，也表示一個組
(?imx)	正則表達式包含三種可選標志：i, m, 或 x 。只影響括號中的區(qū)域。
(?-imx)	正則表達式關(guān)閉 i, m, 或 x 可選標志。只影響括號中的區(qū)域。
(?: re)	類似 (...), 但是不表示一個組
(?imx: re)	在括號中使用i, m, 或 x 可選標志
(?-imx: re)	在括號中不使用i, m, 或 x 可選標志
(?#...)	注釋.
(?= re)	前向肯定界定符。如果所含正則表達式，以 ... 表示，在當前位置成功匹配時成功，否則失敗。但一旦所含表達式已經(jīng)嘗試，匹配引擎根本沒有提高；模式的剩余部分還要嘗試界定符的右邊。
(?! re)	前向否定界定符。與肯定界定符相反；當所含表達式不能在字符串當前位置匹配時成功
(?> re)	匹配的獨立模式，省去回溯。
\w	匹配字母數(shù)字
\W	匹配非字母數(shù)字
\s	匹配任意空白字符，等價于 [\t\n\r\f].
\S	匹配任意非空字符
\d	匹配任意數(shù)字，等價于 [0-9].
\D	匹配任意非數(shù)字
\A	匹配字符串開始
\Z	匹配字符串結(jié)束，如果是存在換行，只匹配到換行前的結(jié)束字符串。c
\z	匹配字符串結(jié)束
\G	匹配最后匹配完成的位置。
\b	匹配一個單詞邊界，也就是指單詞和空格間的位置。例如， 'er\b' 可以匹配"never" 中的 'er'，但不能匹配 "verb" 中的 'er'。
\B	匹配非單詞邊界。'er\B' 能匹配 "verb" 中的 'er'，但不能匹配 "never" 中的 'er'。
\n, \t, 等.	匹配一個換行符。匹配一個制表符。等
\1...\9	匹配第n個分組的子表達式。
\10	匹配第n個分組的子表達式，如果它經(jīng)匹配。否則指的是八進制字符碼的表達式。