Seinfeld
У меня закончились истории. Годами я писал рассказы, некоторые из которых были довольно глупыми, просто чтобы простые проблемы казались сложными, а сложные — простыми. Но, увы, это не тот случай.
Вам дана непустая строка, состоящая исключительно из открывающих и закрывающих фигурных скобок. Ваша задача — определить минимальное количество "операций", необходимых для того, чтобы сделать строку стабильной. Стабильность определяется следующим образом:
Пустая строка является стабильной.
Если S стабильна, то {S} также стабильна.
Если S и T обе стабильны, то ST (конкатенация двух) также стабильна.
Примеры стабильных строк: {}, {}{}, и {{}{}}. Примеры нестабильных строк: }{, {{}{, и {}{.
Единственная разрешенная операция над строкой — это замена открывающей скобки на закрывающую или наоборот.
Входные данные
Ваша программа будет тестироваться на одном или нескольких наборах данных. Каждый набор данных представлен одной строкой. Строка — это непустая последовательность открывающих и закрывающих фигурных скобок и ничего более. Ни одна строка не содержит более 2000 скобок. Все последовательности имеют четную длину.
Последняя строка ввода состоит из одного или нескольких "-" (минус).
Выходные данные
Для каждого тестового случая выведите строку в формате:
k.N
Где k — номер тестового случая (начиная с единицы), а N — минимальное количество операций, необходимых для преобразования данной строки в стабильную.