Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
- пустая строка —– правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
- правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}.
Напишите функцию 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')