10

我希望能够将字符串中的所有括号配对，如果它们没有配对，那么它们会得到它们的索引号和 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
4

9 回答 9

21

您可以将我的代码调整为类似的问题：

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)
于 2011-07-15T01:54:41.863 回答
9 
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
于 2011-07-19T19:45:59.673 回答
4 
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
于 2015-07-06T09:41:50.017 回答
0

谢谢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
于 2011-07-15T15:20:19.497 回答
0

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))
于 2017-01-14T20:17:33.573 回答
0

试试这个：

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)
于 2017-02-05T10:37:04.857 回答
0

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

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")
于 2017-03-30T04:32:32.850 回答
0

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

于 2017-07-01T16:05:35.737 回答
0

我最近的一个项目需要一些东西，并认为我可以在 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()
于 2018-03-30T14:59:27.190 回答