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

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

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)

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

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

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

Answer 5

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

Answer 6

试试这个：

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)

Answer 7

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

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

Answer 8

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

Answer 9

我最近的一个项目需要一些东西，并且认为我可以在 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()