括号匹配（{}[]()<>)问题

Question

我希望能够配对字符串中的所有括号，如果它们没有配对，就会得到它们的索引号和 False。代码似乎在重复一些值，即 cl == pop[1]。我尝试找出问题在哪里，但无论我多么努力，都看不到它。所以我想问是否有人可以帮我找到错误，甚至改进我的代码 ;)

def check_parentheses(string):
    pending = 0
    brackets = []
    '''Checks if parens are paired, otherwise they are bad.'''
    parenstack = collections.deque()
    for ch in string:
        if ch in lrmap:
            try:
                cl = string.index(ch, pending)
                pending = cl + 1

            except:
                cl = False

        if ch in lparens:
            parenstack.append([ch, cl])
            print parenstack

        elif ch in rparens:
            try:
                pop = parenstack.pop()

                if lrmap[pop[0]] != ch:
                    print 'wrong type of parenthesis popped from stack',\
                    pop[0], ch, pop[1], cl

                    brackets.append([pop[1], False])
                    brackets.append([cl, False])
                else:
                    brackets.append([pop[1], cl])

            except IndexError:
                print 'no opening parenthesis left in stack'
                brackets.append([cl, False])

    # if we are not out of opening parentheses, we have a mismatch
    for p in parenstack:
        brackets.append([p[1],False])
    return brackets

- thabubble

---

首先，这个脚本并没有包含运行所需的所有变量。幸运的是，我在网上找到了其余的代码（http://www.python-forum.org/pythonforum/viewtopic.php?f=14&t=5842）。无论如何，您可能想要发布一些示例，说明如何运行该函数，您期望的输出以及实际得到的结果。 - Mark Hildreth

有关标点符号匹配的更多信息，请参见此处：https://dev59.com/VHRB5IYBdhLWcg3wtJGF。 - Patrick Perini

@Patrick：请注意您链接的问题的已接受答案。 - Marcelo Cantos

等我把脚从嘴里拿出来后，我会编辑这篇文章。 - Patrick Perini

Answer 1

你可以将我的代码适应到一个类似的问题：

def Evaluate(str):
  stack = []
  pushChars, popChars = "<({[", ">)}]"
  for c in str :
    if c in pushChars :
      stack.append(c)
    elif c in popChars :
      if not len(stack) :
        return False
      else :
        stackTop = stack.pop()
        balancingBracket = pushChars[popChars.index(c)]
        if stackTop != balancingBracket :
          return False
    else :
      return False
  return not len(stack)

- hughdbrown

---

如果字符串不仅包含圆括号，建议删除最后的"else: return False"，因为它容易造成混淆并需要时间来理解。 - Alex

Answer 2

iparens = iter('(){}[]<>')
parens = dict(zip(iparens, iparens))
closing = parens.values()

def balanced(astr):
    stack = []
    for c in astr:
        d = parens.get(c, None)
        if d:
            stack.append(d)
        elif c in closing:
            if not stack or c != stack.pop():
                return False
    return not stack

例子：

>>> balanced('[1<2>(3)]')
True
>>> balanced('[1<2(>3)]')
False

- pillmuncher

---

@pilmuncher，我喜欢你解决问题的方法。但是我对“return not stack”这个语句有点困惑。不过我从https://dev59.com/8XrZa4cB1Zd3GeqP6b8V上弄清楚了。 - ASANT

@ASANT 或许 return not bool(stack) 更清晰明了？ - hughdbrown

@pilmuncher：我喜欢使用iter()在字符串中交替使用字符。此外，使用dict显然是更好的方法。 - hughdbrown

很好的答案。唯一的问题是balanced('""')没有被处理，相应的开放和关闭字符不能相等。 - Adam Bittlingmayer

Answer 3

BRACES = { '(': ')', '[': ']', '{': '}' }

def group_check(s):
    stack = []
    for b in s:
        c = BRACES.get(b)
        if c:
            stack.append(c)
        elif not stack or stack.pop() != b:
            return False
    return not stack

- Puneet Mahendra

Answer 4

感谢 hughdbrown，你的代码非常容易就能工作，而且非常简短！你刚刚为我解决了一个大问题 :D

如果可以的话，我将其转换为 pep8 格式 :)

编辑

• 增加了对注释和字符串的支持，不会在其中匹配。
• 添加了对易于语言花括号检查的支持，请修改字符集字典。
• 正确地配对，即从右至左

HTML

charset = dict(opening='{[(<',\
    closing='}])>',\
    string = ('"', "'"),\
    comment=(('<!--', '-->')))

Python

charset = dict(opening='{[(<',\
    closing='}])>',\
    string = ('"', "'"),\
    comment=(("'''", "'''"), ('"""', '"""'), ('#', '\n')))

C++

charset = dict(opening='{[(<',\
    closing='}])>',\
    string = ('"', "'"),\
    comment=(('/*', '*/'), ('//', '\n')))

你懂的吧？ :)

charset = dict(opening='{[(<',\
    closing='}])>',\
    string = ('"', "'"),\
    comment=(('<!--', '-->'), ('"""', '"""'), ('#', '\n')))

allowed = ''.join([x[0][0] + x[1][0] for x in charset['comment']])
allowed += ''.join(charset['string'])
allowed += charset['opening']
allowed += charset['closing']

def brace_check(text):
    o = []
    c = []
    notr = []
    found = []
    busy = False
    last_pos = None
    for i in xrange(len(text)):
        ch = text[i]
        if not busy:
            cont = True
            for comment in charset['comment']:
                if ch == comment[0][0]:
                    como = text[i:len(comment[0])]
                    if como == comment[0]:
                        busy = comment[1]
                        if ch in charset['opening']:
                            last_pos = i
                        cont = False
                        break
            if cont:
                if ch in charset['string']:
                    busy = ch
                elif ch in charset['opening']:
                    o.append((ch, i))
                elif  ch in charset['closing']:
                    c.append((ch, i))
        else:
            if ch == busy[0]:
                if len(busy) == 1:
                    comc = ch
                else:
                    comc = text[i:i + len(busy)]
                if comc == busy:
                    if last_pos is not None:
                        if busy[-1] in charset['closing']:
                            found.append((last_pos, i))
                        last_pos = None
                        text = text[:i] + '\n' * len(comc) +\
                            text[i + len(comc):]
                    busy = not busy
            elif busy in charset['string']:
                if ch == '\n':
                    busy = not busy
    for t, e in reversed(o):
        try:
            n = next((b, v) for b, v in c\
                if b == charset['closing'][\
                    charset['opening'].find(t)] and v > e)
            c.remove(n)
            n = n[1]
            if found != []:
                if e < found[-1][0] and n > found[-1][0] and n < found[-1][1]\
                or e < found[-1][1] and n > found[-1][1] and e > found[-1][0]:
                    found.append((n, False))
                    n = False
        except StopIteration:
            n = False
        found.append((e, n))
    for t, e in c:
        found.append((e, False))
    return found

- thabubble

---

代码非常复杂，很难阅读。我建议将其发布在codereview.stackexchange.com上，以获取一些建议来简化它。 - Winston Ewert

我同意@Winston的观点，首先删除大部分空行。 - John Machin

嗯，我认为这样格式化更容易阅读。 有趣的是每个人都有不同的想法，我很快就会更新它， 找到了一些更多的错误 :) - thabubble

Answer 5

我最近需要一个东西来完成一个项目，于是想着可以在 OP 的解决方案上进行一些改进。它允许检查注释模式、引用和括号，同时忽略周围的文本。我特意将其设计得比实际需要更加通用，以便其他人可以根据自己的需求取舍。

"""
This module is for testing bracket pairings within a given string
Tested with Python 3.5.4
>>> regexp = getRegexFromList(opening + closing)
>>> print(regexp)
(\\<\\-\\-|\\-\\-\\>|\\/\\*|\\/\\/|\\*\\/|\\#|\\"|\\'|\\(|\\[|\\{|\\<|\\\n|\\\n|\\"|\\'|\\)|\\]|\\}|\\>)
>>> test_string = 'l<--([0])-->1/*{<2>}*/3//<--4 &-->\\n5#"6"\\n7"/*(8)*/"9\'"10"\'11({12\ta})13[<14>]'
>>> patterns = re.findall(regexp, test_string)
>>> print(patterns)
['<--', '(', '[', ']', ')', '-->', '/*', '{', '<', '>', '}', '*/', '//', '<--', '-->', '\\n', '#', '"', '"', '\\n', '"', '/*', '(', ')', '*/', '"', '(', '{', '}', ')', '[', '<', '>', ']']
>>> doBracketsMatch(patterns)
True
>>> doBracketsMatch(['"', ')', '"', '[', ']', '\\''])
False
"""


# Dependencies
import re


# Global Variables
# Provide opening and closing patterns, along with their priorities & whether a priority is nestable
opening =  ['<--', '/*', '//',  '#', '"', '\'', '(', '[', '{', '<']
closing =  ['-->', '*/', '\n', '\n', '"', '\'', ')', ']', '}', '>']
priority = [    1,    1,    1,    1,   1,    1,   0,   0,   0,   0]
nestable = {0: True, 1: False}
bracket_pairs = dict(zip(opening + closing, \
                         [[(closing + opening)[i], (priority + priority)[i]] \
                          for i in range(0, opening.__len__() * 2)]))


def getRegexFromList(listOfPatterns):
    """
    Generate the search term for the regular expression
    :param listOfPatterns:
    :return:
    >>> getRegexFromList(['"', '<--', '##', 'test'])
    '(\\\\t\\\\e\\\\s\\\\t|\\\\<\\\\-\\\\-|\\\\#\\\\#|\\\\")'
    """
    # Longer patterns first to prevent false negatives
    search_terms = sorted(listOfPatterns, key=len, reverse=True)
    regex = ""
    for term in search_terms:
        for char in str(term):
            regex = regex + '\\' + char  # Search for all characters literally
        regex = regex + '|'  # Search pattern = (a|b|c)
    return '(' + regex[:-1] + ')'  # Remove excess '|' and add brackets


def doBracketsMatch(list_of_brackets):
    """
    Determine if brackets match up
    :param list_of_brackets:
    :return:
    """
    stack = []
    for bracket in list_of_brackets:
        # Check empty stack conditions
        if stack.__len__() is 0:
            # Check for openings first to catch quotes
            if bracket in opening:
                stack.append(bracket)
            elif bracket in closing:
                return False
            else:
                continue
        # Check for a matching bracket
        elif bracket == bracket_pairs[stack[-1]][0]:
            stack.pop()
        # Ignore cases:
        #  - False positives
        #  - Lower priority brackets
        #  - Equal priority brackets if nesting is not allowed
        elif bracket not in bracket_pairs or \
                bracket_pairs[bracket][1] < bracket_pairs[stack[-1]][1] or \
                (bracket_pairs[bracket][1] == bracket_pairs[stack[-1]][1] and \
                    not nestable[bracket_pairs[bracket][1]]):
            continue
        # New open bracket
        elif bracket in opening:
            stack.append(bracket)
        # Otherwise, unpaired close bracket
        else:
            return False
    # If stack isn't empty, then there is an unpaired open bracket
    return not bool(stack)


if __name__ == '__main__':
    import doctest
    doctest.testmod()

- user3303504

Answer 6

以下代码将显示给定字符串中缺少的括号及其缺失次数。

from collections import Counter

def find_missing(str):
    stack1 = []
    stack2 = []
    result = []
    res_dict = {}
    open_set = '<[{('
    closed_set = '>]})'
    a = list(str)
    for i in a:
        if i in open_set:
            stack1.append(i)
        elif i in closed_set:
            stack2.append(i)
    dict1 = Counter(stack1)
    dict2 = Counter(stack2)
    print(dict1)
    print(dict2)
    for i in open_set:
        if dict1[i] > dict2[closed_set[open_set.index(i)]]:
            res_dict[closed_set[open_set.index(i)]] = dict1[i] - dict2[closed_set[open_set.index(i)]]
            result.append(closed_set[open_set.index(i)])
    for i in closed_set:
        if dict2[i] > dict1[open_set[closed_set.index(i)]]:
            res_dict[open_set[closed_set.index(i)]] = dict2[i] - dict1[open_set[closed_set.index(i)]]
            result.append(open_set[closed_set.index(i)])
    return res_dict
    # return result

if __name__ == '__main__':
    str1 = '{This ((()bracket {[function]} <<going> crazy}'
    x = find_missing(str1)
    if len(x) > 0:
        print("Imbalanced")
        print(x)
    else:
        print("Balanced")

- Ramesh Ganesan

Answer 7

首先，我们将从左到右扫描字符串，并且每次看到一个开括号时，我们将其推入堆栈中，因为我们希望最后一个开括号首先关闭。（记住堆栈的FILO结构！） 然后，当我们看到一个闭括号时，我们检查最后打开的括号是否是相应的闭合匹配，通过从堆栈中弹出一个元素。如果它是有效的匹配，则继续前进，否则返回false。 代码： https://gist.github.com/i143code/51962bfb1bd5925f75007d4dcbcf7f55

- ASHISH R

Answer 8

一个在 Python 3 中易于理解的解决方案：

def check_balanced_string(str):
  stack = []
  dicc = {'(': ')', '[': ']', '{': '}'}
  for char in str:
    if char in dicc.keys():  # opening char
      stack.append(char)
    elif char in dicc.values():  # closing char
      if dicc[stack[-1]] == char:  # check if closing char corresponds to last opening char
        stack.pop()
      else:
        return False
  return not len(stack)  # returns True when len == 0

eq = '{1+[3*5+(2+1)]}'
print(check_balanced_string(eq))

- alvarezfmb

Answer 9

试试这个：

def matched(s):
stack=[]
open,close="(",")" 
for i in s:
    if i in open:
        stack.append(i)
    if i in close:
        if len(stack)==0:
            return(False)
        else:   
            stack.pop()
if len(stack):
    return(False)
else:
    return(True)

- Balaji

---

虽然这段代码可能回答了问题，但提供有关它如何以及/或为什么解决问题的附加上下文将改善答案的长期价值。 - Donald Duck