Question

Назовём скобочную последовательность, состоящую из трёх видов скобок (круглых, квадратных или фигурных) , если она может быть построена по следующим правилам: Пустая последовательность является правильной.Если A — правильная скобочная последовательность, то {A}, [A] и (A) — правильные скобочные последовательности.Если A и B — правильная скобочная последовательность, то AB — правильная скобочная последовательность.Иначе говоря, правильная скобочная последовательность получается, если мы берём какое-то математическое выражение с корректно расставленными скобками и убираем оттуда всё, кроме скобок.Вам дана скобочная последовательность длины N. Вам разрешено вставлять скобки в любое место последовательности (в начало, в конец и между двумя любыми скобками). Ваша задача — добавить не более N скобок так, чтобы последовательность превратилась в правильную.Разберём три примера к задаче. В первом примере все три скобки добавлены в конец — мы закрываем уже открытые скобки. Во втором примере последовательность и так является правильной. Можно вывести её, можно, к примеру, добавить ещё пару скобок — минимальность ответа не требуется. В третьем примере последовательность правильной не является — скобки закрываются не в том порядке. Можно исправить, например, вставив открывающую квадратную скобку сперели и закрывающую квадратную — перед закрывающей фигурной.Формат вводаНа вход подаётся непустая строка из не более, чем 104 символов, состоящая из символов ‘{’, ‘}’, ‘[’, ‘]’, ‘(’ и ‘)’.Формат выводаВыведите итоговую строку, получившуюся после вставки скобок и являющуюся правильной скобочной последовательностью. Длина строки не должна превышать удвоенной длины входной строки. Если ответов несколько, выведите любой. Минимизировать длину строки не требуется.Пример 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.

Answer 2

Вот пример решения задачи на языке Python:

pythonCopy code
def insert_brackets(sequence):
    stack = []
    result = ""

    for char in sequence:
        if char in ['(', '[', '{']:
            stack.append(char)
        elif char in [')', ']', '}']:
            if len(stack) > 0:
                opening_bracket = stack.pop()
                if (char == ')' and opening_bracket != '(') or \
                   (char == ']' and opening_bracket != '[') or \
                   (char == '}' and opening_bracket != '{'):
                    # Не совпадают открывающая и закрывающая скобки, вставляем соответствующую пару
                    result += opening_bracket + char
            else:
                # Нет открывающей скобки, вставляем соответствующую пару
                result += get_matching_bracket(char)
        result += char

    # Добавляем оставшиеся открывающие скобки в конец
    while len(stack) > 0:
        opening_bracket = stack.pop()
        result += get_matching_bracket(opening_bracket)

    return result


def get_matching_bracket(bracket):
    if bracket == '(':
        return ')'
    elif bracket == ')':
        return '('
    elif bracket == '[':
        return ']'
    elif bracket == ']':
        return '['
    elif bracket == '{':
        return '}'
    elif bracket == '}':
        return '{'


# Считываем входные данные
sequence = input()

# Вставляем скобки и выводим результат
result = insert_brackets(sequence)
print(result)

Примеры использования:

1. Ввод: ( [ {( ) [ ] { }. Вывод: ( [ {( ) [ ] { } ) ] }.
2. Ввод: ( [ ]. Вывод: ( [ ] ).
3. Ввод: { [ } ]{ } [ ]. Вывод: { [ } ]{ } [ ].