Minimum cost of a correct parenthesization (1) P76915


Statement
 

pdf   zip

thehtml

Given a word made up of only opening and closing parentheses, we must make it a correct parenthesization. The only allowed operation is turning each parenthesis, that is, changing its orientation. What is the minimum number of turns needed?

For example, if the word is “)(()((()”, then we can achieve the correct parenthesization “((())())” just turning three parentheses, and we cannot do better.

Input

Input consists of several cases, each with a word with n opening or closing parentheses. You can assume that n is even and between 2 and 100.

Output

For every case, print the minimum cost of a correct parenthesization.

Hint

Although there are more efficient solutions, a dynamic programming with time cost Θ(n3 ) and space cost Θ(n2 ) should be enough.

Public test cases
  • Input

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

    Output

    0
    0
    1
    2
    2
    2
    3
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++