Помогие решить Заменить до правильной скобочной последовательности

Question

Помогие решить Заменить до правильной скобочной последовательности

Ирина Александрова Ученик (84), закрыт 2 недели назад

ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Заменить до правильной скобочной последовательности
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Вам задана строка s, состоящая из открывающих и закрывающих скобок четырех видов <>, {}, [], (). Все скобки делятся на два типа: открывающие и закрывающие. Разрешается заменить любую скобку на любую другую такого же типа. Например, скобку < можно заменить на скобку {, но нельзя заменить на скобку ) или >.

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

Определим правильную скобочную последовательность. Пустая строка считается таковой. Пусть строки s1 и s2 являются правильными скобочными последовательностями, тогда строки <s1>s2, {s1}s2, [s1]s2, (s1)s2 также являются правильными скобочными последовательностями.

Например, строка "[[(){}]<>]" является правильной скобочной последовательностью, а строки "[)()" и "][()()" — нет.

Определите наименьшее количество замен, необходимое для того, чтобы сделать строку s правильной скобочной последовательностью.

Входные данные
Единственная строка содержит непустую строку s, состоящую только из открывающих и закрывающих скобок, заданных четырех видов. Длина строки s не превосходит 106.

Выходные данные
Если получить правильную скобочную последовательность из строки s невозможно выведите слово Impossible.

Иначе выведите наименьшее количество замен, необходимое для получения правильной скобочной последовательности из строки s.

Примеры
Входные данные
[<}){}
Выходные данные
2
Входные данные
{()}[]
Выходные данные
0
Входные данные
]]
Выходные данные
Impossible

Answer 1

Собственно, первую половину алгоритма нейросеть в соседнем ответе написала вполне правильно. Но вот после цикла начала нести бред.

 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])

Answer 2

 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)