<PREV Problem:
NEXT>
Solved by 628 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Bracket structure correction

Time limit = 2 second(s)

Given the string of '(' and ')' you are to find the minimal number of corrections that is nessesary to do in it to make this string to be a correct bracket structure. Correction = changement the bracket to the different one.

Right bracket structure can be defined as follows:

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

Here are correct bracket structures:

    ()()()
	(())()
	((((()))))
Here are INcorrect bracket structures

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

Input. One or more lines, containing symbols '(' and ')' of total length lesser than 1000.

Output. Minimal number of corrections. If there is no way to correct the input string, you are to output "NO".

Input#1
((((
Output#1
2

Input#2
((()

Output#2
1

Input#3
(((

Output#3
NO

Author:
Folklore
3 March 2005

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.158.248.167