Сопряжение скобок({}[]()) выпуск

Я хочу иметь возможность соединить все скобки в строку, если они не спарены, то они получают свой номер индекса и 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
776   9  

9 ответов:

Вы можете адаптировать мой код к аналогичному вопросу: 

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)
19  
2011-07-15 04:54:41 
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
9  
2011-07-19 22:45:59 
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  
2015-07-06 12:41:50

Спасибо hughdbrown ваш код был ветерком, чтобы начать работать, и это действительно коротко! Вы только что избавили меня от головной боли: D

Преобразовал его в pep8, если это нормально :)

Edit

  • добавлена поддержка комментариев и строк, она не будет совпадать внутри них.
  • добавлена поддержка легкой проверки языковых скобок, измените кодировку dict.
  • Правильно paires up, то есть право на слева

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
0  
2011-07-21 23:56:39

Понятное решение в 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))
0  
2017-01-14 22:17:33

Попробуйте это:

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)
0  
2017-02-05 15:00:23

Приведенный ниже код будет отображать отсутствующие скобки и число раз, отсутствующих в данной строке.

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")
0  
2017-03-30 07:32:32

Сначала мы будем сканировать строку слева направо, и каждый раз, когда мы видим открывающую скобку, мы помещаем ее в стек, потому что мы хотим, чтобы последняя открывающая скобка была закрыта первой. (Вспомните структуру FILO стека!) Затем, когда мы видим закрывающую скобку, мы проверяем, является ли последняя открытая скобка соответствующим закрывающим соответствием, выскакивая элемент из стека. Если это действительно совпадение, то мы идем вперед, если не возвращаемся ложный. Код: https://gist.github.com/i143code/51962bfb1bd5925f75007d4dcbcf7f55

0  
2017-07-01 19:05:35

Мне нужно было что-то для недавнего проекта, и я решил, что могу немного развить решение ОП. Он позволяет проверять шаблоны комментариев, кавычки и скобки, игнорируя при этом окружающий текст. Я намеренно сделал его более общим, чем это должно быть, чтобы другие могли взять то, что они хотят, и вырезать то, что они не делают. 

"""
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()
0  
2018-04-02 15:57:19

Comments

    Ничего не найдено.
Click here to cancel reply.