Правильная скобочная последовательность стек python [дубликат]

#python #стек

        
             
                
                    
                        
                            На этот вопрос уже даны ответы здесь:
                            
                        
                    
                
                        
                            Проверить правильно ли вложены скобки 〈 ( { [ ] } ) 〉в
тексте
                                
                                    (2 ответа)
                                
                        
                                Закрыт 2 года назад.
            
                    
Всем привет, кто может помочь с реализацией проверки на правильность скобочной последовательности
через стек на 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

    

Ответы

Ответ 1

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

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


Ответ 2

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

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

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

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