Дана последовательность \(s\), состоящая из скобок двух типов: '(', ')', '[' и ']'.
Строка называется правильной скобочной последовательностью (ПСП), если она одного из следующих типов:
- пустая строка;
- '(' + ПСП + ')';
- '[' + ПСП + ']';
- ПСП + ПСП.
где плюс — это операция склеивания двух строк.
За один ход можно выбрать непустую подпоследовательность символов строки \(s\) (не обязательно подряд идущих), которые являются ПСП, удалить их из строки и склеить оставшиеся части, не изменяя порядка.
Какое наибольшее количество ходов можно совершить?
Выходные данные
Для каждого набора входных данных выведите одно целое число — наибольшее количество ходов, которые можно совершить с данной строкой \(s\).
Примечание
В первом примере можно просто удалить всю строку.
Во втором примере можно сначала удалить скобки на позициях \(1\) и \(2\): «[]()», затем останется «()». Потом можно удалить строку целиком. Можно было и сразу удалить всю строку, но тогда была бы одна операция вместо двух.
В третьем примере можно сначала удалить скобки на позициях \(1\) и \(3\): «([)]». Они образуют ПСП «()». Затем останется «[]», поэтому можно удалить ее целиком.
В четвертом примере нет ни одной подпоследовательности, которая является ПСП, поэтому нельзя совершить ни один ход.
В пятом примере можно удалить скобки на позициях \(2\) и \(4\): «)[(]» и получить «)(» в результате. Из нее ничего нельзя удалить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
()
[]()
([)]
)]([
)[(]
|
1
2
2
0
1
|