Дана строка из круглых, квадратных и фигурных скобок. Удалите наименьшее число символов так, чтобы оставшиеся образовали правильную скобочную последовательность, и выведите то, что осталось.
Правильная последовательность определяется обычно: пустая строка правильна; если правильна, то , и правильны; если и правильны, то и правильна.
Формат ввода
Одна строка из круглых, квадратных и фигурных скобок. Длина не превосходит 700.
Формат вывода
Строка наибольшей длины, являющаяся правильной скобочной последовательностью и получающаяся из исходной удалением символов. Если ответов несколько, выведите любой. Если подходит только пустая строка, выведите пустую строку.
Примеры
ввод
([)]
вывод
[]
ввод
{([(]{)})]
вывод
[({})]
ввод
)(
вывод
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.