Задача из области "алгоритмы и структуры данных".
Дан фрагмент последовательности скобок, состоящей из символов
(){}[]
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте "IMPOSSIBLE".
Максимальная длина строки 10^6 символов.
Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]
Sample Input 2:
{][[[[{}[]
IMPOSSIBLE
Идеи:
Есть стандартный алгоритм проверки корректности расстановки скобок, реализуемый через стэк. Суть в следудующем:
идем по строке, если встречаем открывающую скобку - заносим в стек
если встречаем закрывающую скобку и на вершине стека лежит аналогичная ей открывающая, то удаляем ее (открывающюю) из стека
если после прохода всей строки стек пустой, значит скобки расставлены верно.
Для решения этого задания этот алгоритм нужно модифицировать, чтобы была возможность (или определить невозможность) дополнения проверяемой строки до корректной.
Для этого пытался заводить счетчики на каждую скобку и ее направление и держать
противоположную скобку в деке и в нужный момент извлекать из дека. Но пока все покрывается ифами и алгоритм все равно правильно не работает
Ответ
Привет со Степика!
Держи код, прошедший все тесты в том уроке: Pastebin
В кратце об алгоритме:
открывающие скобки заносим в стек
встречая закрывающие скобки проверяем на соответствие последней в стеке
соответствует -> убираем из стека, иначе -> см.пункт 3
стек пуст? -> выводим слева, иначе -> IMPOSIBLE
если после полного прохода последовательности стек не пуст, дополняем справа
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()
posible = True
cin = input()
a=Stack()
s=Stack()
for i in cin:
if ( i == '(' or i == '[' or i == '{' ):
s.push( i )
if ( i == ')' or i == ']' or i == '}'):
if s.isEmpty():
a.push(i)
else:
temp = s.pop()
if (i == ')' and temp != '(') or (i == ']' and temp != '[') or (i == '}' and temp != '{'):
posible = False
break
if posible:
while not a.isEmpty():
temp = a.pop()
if temp == ']':
temp = '['
if temp == ')':
temp = '('
if temp == '}':
temp = '{'
print(temp, end = '')
print(cin, end = '')
while not s.isEmpty():
temp = s.pop()
if temp == '[':
temp = ']'
if temp == '(':
temp = ')'
if temp == '{':
temp = '}'
print(temp, end = '')
else:
print('IMPOSSIBLE')
