Назовём скобочную последовательность, состоящую из трёх видов скобок (круглых, квадратных или фигурных) , если она может быть построена по следующим правилам:

пустая последовательность является правильной.

если

a

— правильная скобочная последовательность, то

{

a

}

,

[

a

]

и

(

a

)

— правильные скобочные последовательности.

если

a

и

b

— правильная скобочная последовательность, то

a

b

— правильная скобочная последовательность.

иначе говоря, правильная скобочная последовательность получается, если мы берём какое-то выражение с корректно расставленными скобками и убираем оттуда всё, кроме скобок.

вам дана скобочная последовательность длины

n

. вам разрешено вставлять скобки в любое место последовательности (в начало, в конец и между двумя любыми скобками). ваша — добавить не более

n

скобок так, чтобы последовательность превратилась в правильную.

разберём три примера к . в первом примере все три скобки добавлены в конец — мы закрываем уже открытые скобки. во втором примере последовательность и так является правильной. можно вывести её, можно, к примеру, добавить ещё пару скобок — минимальность ответа не требуется. в третьем примере последовательность правильной не является — скобки закрываются не в том порядке. можно исправить, например, вставив открывающую квадратную скобку сперели и закрывающую квадратную — перед закрывающей фигурной.

формат ввода

на вход подаётся непустая строка из не более, чем

1

0

4

символов, состоящая из символов ‘{’, ‘}’, ‘[’, ‘]’, ‘(’ и ‘)’.

формат вывода

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

пример 1

ввод вывод

( [ {

( ) [ ] { }

пример 2

ввод вывод

( [ ] )

( ) [ ] [ ] ( )

пример 3

ввод вывод

{ [ } ]

{ } [ ] { } [ ]

примечания

решением этой должна являться программа на одном из представленных в системе языков программирования, решающая данную . программа должна считывать данные со стандартного ввода (клавиатуры) и выводить на стандартный вывод (монитор). никаких дополнительных строк или символов выводить не разрешается.

в qbasic или паскаль

андрей2149    2   16.11.2019 10:46    3