Проверка на верное количество скобок [ { ( ) } ]

#python #инспекция_кода

Добрый день друзья! Задача следующая, написать код, который проверяет, верно ли расставлены
скобки в выражении т.е.



("(5+5)/[4+4]*{2*2}" - True, "(3+[2*3)]" - False .



Код я написал, честно говоря, показывать конечно стыдно, но увы, никто кроме Вас,
меня умнее не сделает. Просьба - подскажите, как можно сделать из ЭТОГО, нормальный
код? Сам по себе код работает. 



def checkio(expression):
list_backets = []

for i in expression:
    if i == "[" or i == "]" or i == "(" or i == ")" or i == "{" or i == "}":
        list_backets.append(i) //создаю список нужных нам элементов

if len(list_backets) == 0: //если нет элементов вовсе
    return True

elif list_backets.count("[") == list_backets.count("]") and list_backets.count("(")
== list_backets.count(")") and list_backets.count("{") == list_backets.count("}"):
  //если количество "(" равно количеству ")" и так далее...
    j = 0
    try:
        while j != range(len(list_backets)): //попытка найти в списке соседние скобки
            if list_backets[j] == "(" and list_backets[j+1] == ")":
                list_backets.pop(j)
                list_backets.pop(j)
                j = 0
            elif list_backets[j] == "{" and list_backets[j+1] == "}":
                list_backets.pop(j)
                list_backets.pop(j)
                j = 0
            elif list_backets[j] == "[" and list_backets[j+1] == "]":
                list_backets.pop(j)
                list_backets.pop(j)
                j = 0
            else:
                j += 1

    except:
        if (len(list_backets)) == 0:
            return True
        else:
            return False

else:
        return False




Выглядит стремно и неуклюже, если у Вас будет возможность и время, расскажите как
сделать его более "красивым" с пояснениями.
Спасибо!
    

Ответы

Ответ 1

Используйте проверку правописания

list_backets -> brackets


Заодно имя типа (list) здесь не обязательно. brackets почти в каждой строчке используется
и само по себе достаточно читаемо.

Возвращайте булевы выражения напрямую

Вместо:

if (len(list_backets)) == 0:
    return True
else:
    return False


Можно писать просто:

return (not list_brackets)


пустые коллекции в Питоне рассматриваются False в булевом контексте

Избегайте bare except:, которое ловит все типы исключений

Эта конструкция перехватывает даже KeyboardInterrupt (Ctrl+C) и SystemExit (выход
из скрипта, реализация sys.exit())—это нежелательно. Ловите только те типы исключений,
которые вы ожидаете, иначе вы можете проигнорировать ошибки во вводе или ошибки, вызванные
багом в коде—неожиданные ошибки должны прекращать скрипт в данном случае.

В Питоне иногда позволительно использовать исключения для управлением потока кодом,
но фактически использование следует ограничить случаями, когда это заметно упрощает
код улучшает его читаемость, эффективность.

В коде в вопросе, использование перехвата исключений указывает на проблему с организацией
цикла. Следует переорганизовать код, чтобы вообще исключить try/except в данном случае.

Сравнение целого числа с range() это баг

Замените j != range(len(list_backets)) на j != len(brackets)

Избегайте управление переменной цикла в ручную. Обходите коллекции напрямую.

То есть вместо:

j = 0
while j != len(brackets):
    print(brackets[j])
    j += 1


Пишите:

for bracket in brackets:
    print(bracket)


Ваш алгоритм требует управления переменной цикла, что делает его менее понятным и
(в данном случае) менее эффективным (выглядит как квадратичный алгоритм). Для сравнения,
вот линейный алгоритм, который обходит коллекцию напрямую.

Используйте # вместо // для комментариев в Питоне

Избегайте излишнего дублирования кода

Вместо:

i == "[" or i == "]" or i == "(" or i == ")" or i == "{" or i == "}"


Можно написать:

character in "[](){}"


В данном случае все скобки представлены одним символом. Чтобы поддерживать скобки
из нескольких символов, можно в кортеж положить:

token in ('>>', '<<', ']', '[', '}', '{')


Вместо:

(list_backets.count("[") == list_backets.count("]")
 and list_backets.count("(") == list_backets.count(")")
 and list_backets.count("{") == list_backets.count("}"))


можно написать:

all(brackets.count(opening) == brackets.count(closing)
    for opening, closing in zip("[({", "])}"))


Небольшое повторение кода может быть полезно. В крайности впадать не следует. Смотрите
по ситуации, какой код более понятен и легче изменять, не поломав, через полгода, когда
детали забудутся.


Ответ 2

list_backets.pop(j)
            list_backets.pop(j)
            j = 0



Эти куски кода явно повторяются, поэтому нет смысла делать 3 разных if'а. Условия
вполне можно записать через or.


except:
    if (len(list_backets)) == 0:
        return True
    else:
        return False



Проверка на пустую строку уже была. Почему она тут второй раз? И почему вообще ожидается,
что тут произойдёт исключение? Сто-то тут надо переделать, наверное.


            list_backets.pop(j)
            list_backets.pop(j)



Если я правильно понимаю, это удаление из середины списка? Да ещё и дважды (по разу
на каждую скобку). Обычно это крайне неэффективно, хотя про питон сказать не могу.


    list_backets.append(i) //создаю список нужных нам элементов



А зачем скобки в отдельном списке? Можно проходить по строке и сразу обрабатывать.



Предлагаю такое решение:

Завести набор скобок (6 штук) и словарь из соответствий закрывающих скобок открывающим
(закрывающая - ключ, открывающая - значение).

завести пустой стек

для каждого символа строки
  если он присутствует в наборе скобок
    если он отсутствует в словаре соответствий, т. е. это открывающая скобка
      добавить в стек этот символ
    иначе он закрывающая скобка
      если значение из словаря соответствий отличается от вершины стека
        return false
      иначе
        выкинуть последний элемент стека

return стек пуст


Ответ 3

Думаю наилучшим решением будет использование стека и постоянное удаление элементов
в нем, если скобки открывающаяся и закрывающаяся совпадают, то они очищаются из стека
и так до тех пор, пока он не окажется пустым.  

def check(string):
brackets_open = ('(', '[', '{', '<')
brackets_closed = (')', ']', '}', '>')
stack = []
for i in string:
    if i in brackets_open:
        stack.append(i)
    if i in brackets_closed:    
        if len(stack) == 0:
            return False
        index = brackets_closed.index(i)
        open_bracket = brackets_open[index]
        if stack[-1] == open_bracket:
            stack = stack[:-1]  
        else: return False  
return (not stack)  


Применение очень простое:
создаем строки которые нужно проверить на правильность.

str1 = '[{([[[<>]]])(<>)(){}}]' 
str2 = ']()(){<>}[[()]]' 
str3 = '[(sjd),"2"],{2:3}, [<>]'
str4 = '{[[[[((()))]]<]>]}'


Затем применяем к ним функцию:

print(check(str1))  #True
print(check(str2))  #False
print(check(str3))  #True
print(check(str4))  #False


Ответ 4

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

class ElectronPositronValidator:
    def __init__(self):
        self.op_brackets = ("(", "[", "{", "<")
        self.clos_brackets = (")", "]", "}", ">")
        self.opposite_brackets = {"(": ")",
                                  "[": "]",
                                  "{": "}",
                                  "<": ">"}
        self.bracket_dump = ""

    def _add_to_dump(self, bracket):
        self.bracket_dump = self.bracket_dump + bracket
        if bracket in self.clos_brackets:
            # Проверим на предмет аннигиляции две последние скобки
            if len(self.bracket_dump) >= 2 and \
               self.bracket_dump[-1] == self.opposite_brackets.get(self.bracket_dump[-2],
None):
                self._annihilate()

    def _annihilate(self):
        self.bracket_dump = self.bracket_dump[:-2]

    def is_valid(self, target_string):
        self.bracket_dump = ''
        for char in target_string:
            if char in self.op_brackets or char in self.clos_brackets:
                self._add_to_dump(char)
        if self.bracket_dump:
            return False
        else:
            return True


validator = ElectronPositronValidator()
print(validator.is_valid("(5+5)/[4+4]*{2*2}"))
print(validator.is_valid("()()()()()()()()()()"))
print(validator.is_valid("([{<|>}])"))
print(validator.is_valid("3[||:||]Ɛ"))
print(validator.is_valid(""))

print(validator.is_valid("(3+[2*3)]"))
print(validator.is_valid("()()()()()()()()()("))
print(validator.is_valid("()[]{}<>}{"))
print(validator.is_valid("({{[[  >  ]]}})"))
print(validator.is_valid(">([])<"))


Ответ 5

Добра всем!
Случайно набрел на этот пост и вот что придумал:
1. Как минимум должно быть четное количество скобок - открыли\закрыли.
2. Использовать regex!

import re
exp = '{*08/)348+124[7{)7{/[){5[}506(}*178][]/-{71)]7[19{05{-{*)}7(5+2)54]43-*2+(*74]{44}){52{/{0]88{(})9}90}}50[)(*41{{8+)-/38/5/*({0(-28*21/8{+{*9*22-/269+44-[/)298043{40]75/-1[4[26(/4]3-{71-]{554}65*6{20558*6{*/32)-{6++*/92]+623{1-59+/749291)161)(((-21-+++[0138)3*3+]+3{[4)952})124/3]9/)]/2+})(-964}'
exp_mod = ''.join([el for el in exp if el in ('(',')','{','}','[',']')]) #убираем
все кроме скобок
if len(exp_mod) % 2 != 0:
    print(False) #если нечетно количество - сразу в утиль
elif len(re.findall(r'\((?=[\]\}])|\[(?=[\)\}])|\{(?=[\)\]])', exp_mod)) > 0:
    print(False) #если после открытия сразу есть иное закрытие (например, после '{'
идет ']')- тоже в утиль
else: # ищем соотв пары '()','[]','{}' и те же пары, только с 2, 4 и далее другими
скобками м/у ними - ну тут напутано, можно и попроще
    pattern = r'\(\)|\[\]|\{\}|\(.{2}\)|\[.{2}\]|\{.{2}\}|\(.{4}\)|\[.{4}\]|\{.{4}\}|\(.{'
+ str(len(exp_mod)-4) + '}\)|\[.{' + str(len(exp_mod)-4) + '}\]|\{.{' + str(len(exp_mod)-4)
+ '}\}|\(.{' + str(len(exp_mod)-2) + '}\)|\[.{' + str(len(exp_mod)-2) + '}\]|\{.{'
+ str(len(exp_mod)-2) + '}\}|\(.{' + str(len(exp_mod)-8) + '}\)|\[.{' + str(len(exp_mod)-8)
+ '}\]|\{.{' + str(len(exp_mod)-8) + '}\}'
    if len(re.sub(pattern, '', exp_mod)) > 0:
        print(False)            
    else:
        print(True)