stack, cnt, sym = [], 0, {'[':']', '{':'}', '(':')', '<':'>'}
for ch in input():
if ch in sym:
stack.append(sym[ch])
elif not stack:
stack.append('@')
break
else:
cnt += ch != stack.pop()
print(['Impossible', cnt][not stack])
s = input().strip()
stack = []
replacements = 0
opening = {'<', '{', '[', '('}
closing = {'>', '}', ']', ')'}
pairs = {'<': '>', '{': '}', '[': ']', '(': ')'}
for char in s:
if char in opening:
stack.append(char)
elif char in closing:
if not stack:
print("Impossible")
exit()
last_open = stack.pop()
if pairs[last_open] != char:
replacements += 1
if stack:
if len(stack) % 2 != 0:
print("Impossible")
else:
replacements += len(stack) // 2
exit()
print(replacements)
ограничение по памяти на тест256 мегабайт
Заменить до правильной скобочной последовательности
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Вам задана строка s, состоящая из открывающих и закрывающих скобок четырех видов <>, {}, [], (). Все скобки делятся на два типа: открывающие и закрывающие. Разрешается заменить любую скобку на любую другую такого же типа. Например, скобку < можно заменить на скобку {, но нельзя заменить на скобку ) или >.
Далее приводится стандартное определение правильной скобочной последовательности, с которым вы возможно уже знакомы.
Определим правильную скобочную последовательность. Пустая строка считается таковой. Пусть строки s1 и s2 являются правильными скобочными последовательностями, тогда строки <s1>s2, {s1}s2, [s1]s2, (s1)s2 также являются правильными скобочными последовательностями.
Например, строка "[[(){}]<>]" является правильной скобочной последовательностью, а строки "[)()" и "][()()" — нет.
Определите наименьшее количество замен, необходимое для того, чтобы сделать строку s правильной скобочной последовательностью.
Входные данные
Единственная строка содержит непустую строку s, состоящую только из открывающих и закрывающих скобок, заданных четырех видов. Длина строки s не превосходит 106.
Выходные данные
Если получить правильную скобочную последовательность из строки s невозможно выведите слово Impossible.
Иначе выведите наименьшее количество замен, необходимое для получения правильной скобочной последовательности из строки s.
Примеры
Входные данные
[<}){}
Выходные данные
2
Входные данные
{()}[]
Выходные данные
0
Входные данные
]]
Выходные данные
Impossible