Выражение со скобками

Дана строка S, содержащая только десятичные цифры, знаки арифметических операций «+», «-», «*» и «/», а также круглые, квадратные и фигурные скобки: «(», «)», «[», «]», «{», «}».

Назовем выражение корректным, если:

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

Примеры корректных выражений:

        [{1+2}(3+++4)]

        [(1***2){3}45]

Примеры некорректных выражений:

        (1+2]) – (лишняя закрывающая скобка ]);

        (1+2] – (открывающая и закрывающая скобки не соответствуют друг другу).

Определите максимальное количество символов в непрерывной последовательности текста строки S, которая представляет собой корректное выражение.

Входные данные

Входной файл INPUT.TXT содержит непустую строку S, состоящую не более чем из 10⁶ символов из следующего множества: десятичные цифры, знаки арифметических операций «+», «-», «*» и «/», а также круглые, квадратные и фигурные скобки: «(», «)», «[», «]», «{», «}». Гарантируется, что строке S присутствуют корректные выражения.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – максимально возможное количество символов в искомой подпоследовательности строки S.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]