6

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

def brackets_check(s):
meetings = 0
for c in s:
    if c == '(':
        meetings += 1
    elif c == ')':
        meetings -= 1
        if meetings < 0:
            return False

return meetings == 0
2
  • 3
    Приложите ваш код. Если вы сделали с помощью счетчика, то в некотором смысле этот счетчик и есть стек (когда вы добавляете туда 1, вы как бы туда кладёте открывающуюся скобку, а когда встречаете закрывающуюся - то достаете оттуда)
    – Darth
    21 июн 2017 в 17:57
  • Я указала, что через условия делала. а не через счётчик
    – Darkness
    21 июн 2017 в 19:41

2 ответа 2

12

На самом деле, всё очень просто.

Вы идёте от начала строки. Каждый раз, когда встречаете открывающую скобку - кладёте её в стек. Каждый раз, когда встречаете закрывающую - убираете из стека ранее положенную скобку.

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

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

2
  • Спасибо вам большое, очень понятно!
    – Darkness
    21 июн 2017 в 18:51
  • Простое и легкое объяснение!
    – hellog888
    14 авг 2022 в 7:01
8

А мне понравился этот простой и хитрый алгоритм – главное чтобы строка в нем не имела символом, кроме ()[]{}, там даже объяснять ничего не нужно:

def is_correct_brackets(text):
    while '()' in text or '[]' in text or '{}' in text:
        text = text.replace('()', '')
        text = text.replace('[]', '')
        text = text.replace('{}', '')

    # Возвращаем True, если text с пустой строкой
    return not text


print(is_correct_brackets('(((())))'))  # True
print(is_correct_brackets('(((())'))  # False
print(is_correct_brackets('())))'))  # False
print(is_correct_brackets('((((){}[]{}[])))'))  # True
print(is_correct_brackets('(){}[]{}[])))'))  # False
print(is_correct_brackets('(){}[]{}[]'))  # True
3
  • Спасибо большое за предоставленный ответ, все понятно и просто
    – Darkness
    21 июн 2017 в 18:52
  • 1
    Красиво, хотя маленький олимпиадник внутри меня возмущается, что этот алгоритм имеет квадратичную сложность против линейной сложности алгоритма со стеком. И, кстати, в вопросе было указано, что нужен именно вариант со стеком.
    – Xander
    21 июн 2017 в 18:56
  • @Александр, поэтому я и не стал выкладывать код с стеком :)
    – gil9red
    21 июн 2017 в 21:10

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.