Скобочная последовательность

Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.

Дана скобочная последовательность. Нужно определить, правильная ли она.

Будем придерживаться такого определения:

  • пустая строка —– правильная скобочная последовательность;
  • правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
  • правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.

На вход подаётся последовательность из скобок трёх видов: [], (), {}.

Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.

Формат ввода

На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.

Формат вывода

Выведите «True» или «False».

class Stack:    
    def __init__(self):
            self.items = []
    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

line = list(input())
d = {'(':')','{':'}','[':']'}
s = Stack()
for x in line:
    if x in d.keys():
        s.push(x)
    elif not s.isEmpty() and d[s.peek()] == x:
        s.pop()
    else:
        s.push(x)
        break
if s.isEmpty():    
    print('True')
else:
    print('False')


Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий