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
Darkness
  • 103
  • 3
    Приложите ваш код. Если вы сделали с помощью счетчика, то в некотором смысле этот счетчик и есть стек (когда вы добавляете туда 1, вы как бы туда кладёте открывающуюся скобку, а когда встречаете закрывающуюся - то достаете оттуда) – Darth Jun 21 '17 at 17:57
  • Я указала, что через условия делала. а не через счётчик – Darkness Jun 21 '17 at 19:41

2 Answers2

12

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

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

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

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

Xander
  • 20,499
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
gil9red
  • 77,085
  • Спасибо большое за предоставленный ответ, все понятно и просто – Darkness Jun 21 '17 at 18:52
  • 1
    Красиво, хотя маленький олимпиадник внутри меня возмущается, что этот алгоритм имеет квадратичную сложность против линейной сложности алгоритма со стеком. И, кстати, в вопросе было указано, что нужен именно вариант со стеком. – Xander Jun 21 '17 at 18:56
  • @Александр, поэтому я и не стал выкладывать код с стеком :) – gil9red Jun 21 '17 at 21:10