Question

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

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

Если

A

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

{

A

}

,

[

A

]

и

(

A

)

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

Если

A

и

B

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

A

B

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

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

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

N

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

N

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

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


Формат ввода

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

1

0

4

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

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

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

Пример 1

Ввод Вывод

( [ {

( ) [ ] { }

Пример 2

Ввод Вывод

( [ ] )

( ) [ ] [ ] ( )

Пример 3

Ввод Вывод

{ [ } ]

{ } [ ] { } [ ]

Примечания

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

В qbasic или Паскаль

Answer 1

===== PascalABC.NET =====

begin

 var s := ReadlnString;

 var t := '';

 foreach var c in s do

   case c of

     '(': t += c + ')';

     '[': t += c + ']';

     '{': t += c + '}';

     ')': t += '(' + c;

     ']': t += '[' + c;

     '}': t += '{' + c

   end;

 Write(t)

end.