printЗанятие 9

printD. Скобки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Определим правильные скобочные выражения так:
  • Пустое выражение – правильное.
  • Если выражение `S` правильное, то (`S`) и [`S`] также правильные.
  • Если выражения `A` и `B` правильные, то и выражение `"AB"` – правильное.
Дана последовательность из скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.
Ограничения: исходная последовательность содержит не более 100 скобок.
Ввод
В первой строке находятся символы (, ), [ и ] без пробелов.
Вывод
Выводится искомая последовательность скобок без пробелов.

Пример ввода 1

([(]

Пример вывода 1

()[()]

Пример ввода 2

([[)]]

Пример вывода 2

([[()]])

Пример ввода 3

(([))]

Пример вывода 3

(([]))[]

Пример ввода 4

(([[[))]]]

Пример вывода 4

()()[[[()()]]]
Источник: NEERC, 2001
loading