Назовем строку S правильной скобочной последовательностью, если она состоит только из символов '{', '}', '[', ']', '(', ')' и выполнено хотя бы одно из следующих трех условий:
S - пустая строка;
S можно представить в виде S = S[1]
+ S[2]
+ S[3]
+ ... + S[n]
(n > 1), где S[i]
— непустые правильные скобочные последовательности, а знак "+" обозначает конкатенацию (приписывание) строк;
S можно представить в виде S = { + C + } или S = [ + C + ] или S = ( + C + ), где C является правильной скобочной последовательностью.
Дана строка, состоящая только из символов '{', '}', '[', ']', '(', ')'. Требуется определить, какое минимальное количество символов надо вставить в эту строку для того, чтобы она стала правильной скобочной последовательностью.
Одна строка, состоящая из не более чем 100 символов '{','}', '[',']', '(',')'.
Вывести неотрицательное целое число - ответ на поставленную задачу.