Parentheses pairing ({}[]()<>) issue

问题:

I want to be able to pair up all parentheses in a string, if they aren't paired then then they get their index number and False. It seems like it is repeating some values over and over, i.e cl == pop[1]. I have tried to see where the problem is but I can't see it no matter how hard I try. So I'm asking if anyone help me to locate the error and maybe even improve my code ;)

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

回答1:

You can adapt my code to a similar question:

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)

回答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

Example:

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

回答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

回答4:

Thanks hughdbrown your code was a breeze to get working and it's really short! You've just saved me a headache :D

converted it to pep8 if thats ok :)

Edit

• Added support for comments and strings, it will not match inside them.
• Added support for easy language brace checking, modify the charset dict.
• Correctly paires up, i.e right to left

HTML

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

Python

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

C++

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

you get the point? :)

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

回答5:

An understandable solution in 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))

回答6:

Try this:

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)

回答7:

The below code will display the missing parentheses and the no of times missing in the given string.

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

回答8:

First we will scan the string from left to right, and every time we see an opening parenthesis we push it to a stack, because we want the last opening parenthesis to be closed first. (Remember the FILO structure of a stack!) Then, when we see a closing parenthesis we check whether the last opened one is the corresponding closing match, by popping an element from the stack. If it’s a valid match, then we proceed forward, if not return false. Code: https://gist.github.com/i143code/51962bfb1bd5925f75007d4dcbcf7f55

回答9:

I needed something for a recent project and figured I could build on the OP's solution a bit. It allows for comment patterns, quotes and brackets to be checked, whilst ignoring the surrounding text. I've purposefully made it more generic than it needs to be so that others can take what they want and cut out what they don't.

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