Назовём скобочную последовательность, состоящую из трёх видов скобок (круглых, квадратных или фигурных) , если она может быть построена по следующим правилам:
пустая последовательность является правильной.
если
a
— правильная скобочная последовательность, то
{
a
}
,
[
a
]
и
(
a
)
— правильные скобочные последовательности.
если
a
и
b
— правильная скобочная последовательность, то
a
b
— правильная скобочная последовательность.
иначе говоря, правильная скобочная последовательность получается, если мы берём какое-то выражение с корректно расставленными скобками и убираем оттуда всё, кроме скобок.
вам дана скобочная последовательность длины
n
. вам разрешено вставлять скобки в любое место последовательности (в начало, в конец и между двумя любыми скобками). ваша — добавить не более
n
скобок так, чтобы последовательность превратилась в правильную.
разберём три примера к . в первом примере все три скобки добавлены в конец — мы закрываем уже открытые скобки. во втором примере последовательность и так является правильной. можно вывести её, можно, к примеру, добавить ещё пару скобок — минимальность ответа не требуется. в третьем примере последовательность правильной не является — скобки закрываются не в том порядке. можно исправить, например, вставив открывающую квадратную скобку сперели и закрывающую квадратную — перед закрывающей фигурной.
формат ввода
на вход подаётся непустая строка из не более, чем
1
0
4
символов, состоящая из символов ‘{’, ‘}’, ‘[’, ‘]’, ‘(’ и ‘)’.
формат вывода
выведите итоговую строку, получившуюся после вставки скобок и являющуюся правильной скобочной последовательностью. длина строки не должна превышать удвоенной длины входной строки. если ответов несколько, выведите любой. минимизировать длину строки не требуется.
пример 1
ввод вывод
( [ {
( ) [ ] { }
пример 2
ввод вывод
( [ ] )
( ) [ ] [ ] ( )
пример 3
ввод вывод
{ [ } ]
{ } [ ] { } [ ]
примечания
решением этой должна являться программа на одном из представленных в системе языков программирования, решающая данную . программа должна считывать данные со стандартного ввода (клавиатуры) и выводить на стандартный вывод (монитор). никаких дополнительных строк или символов выводить не разрешается.
в qbasic или паскаль
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.