<ПРЕД Задача:
СЛЕД>
Задачу решили 630 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Исправление скобочной структуры

Time limit = 2 секунд(ы)

Дана строчка из символов '(' и ')'. Найдите минимальное число исправлений, которое нужно сделать, чтобы препратить эту строчку в правильную скобочную структуру.

Исправление = замена одной скобки на противоположенную.

Правильная скобочная сруктура определяется рекурсивно

expr ::= expr expr | (expr) | "()"

Примеры павильных скобочных структур:

    ()()()
	(())()
	((((()))))

Примеры НЕправильных скобочных структур

	)(
	))((
	())(
	))))
	(((()(

Вход. Одна строчка, содержащая символы '(' и ')' длиной менее чем 2000 символов.

Выход. Минимальное число исправлений. Если из данной строчки указанными исправлениями нельзя получить правильную скобочную структуру, то выведите строчку со словом "NO".

Вход#1
((((
Выход#1
2

Вход#2
((()

Выход#2
1

Вход#3
(((

Выход#3
NO

Автор:
Фольклор
4 Марта 2005

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 18.207.98.97