e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Скобки

Назовем строку S правильной скобочной последовательностью, если она состоит только из символов '{', '}', '[', ']', '(', ')' и выполнено хотя бы одно из следующих трех условий:

  1. S - пустая строка;
  2. S можно представить в виде S = S1 + S2 + S3 + ... + Sn (n >1), где Si — непустые правильные скобочные последовательности, а знак "+" обозначает конкатенацию (приписывание) строк;
  3. S можно представить в виде S = { + C + } или S = [ + C + ] или S = ( + C + ), где C является правильной скобочной последовательностью.

Дана строка, состоящая только из символов '{', '}', '[', ']', '(', ')'. Требуется определить, какое минимальное количество символов надо вставить в эту строку для того, чтобы она стала правильной скобочной последовательностью.

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

Одна строка, состоящая из не более чем 100 символов '{','}', '[',']', '(',')'.

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

Вывести неотрицательное целое число - ответ на поставленную задачу.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
{(})
Выходные данные #1
2
Входные данные #2
([{}])

Выходные данные #2
0