Minimum cost of a correct parenthesization (2) P10387


Statement
 

pdf   zip

thehtml

Given a word made up of only opening and closing parentheses and square brackets, we can do two kind of operations:

  • Turning the orientation of a parenthesis or a square bracket. That is, we can convert ‘(’ into ‘)’, ‘)’ into ‘(’, ‘[’ into ‘]’, or ‘]’ into ‘[’. The cost is 1.
  • Transforming a parenthesis into a square bracket or the other way around, but not changing its orientation. That is, we can convert ‘(’ into ‘[’, ‘)’ into ‘]’, ‘[’ into ‘(’, or ‘]’ into ‘)’. The cost is 2.

What is the minimum cost of converting a given word into a correct parenthesization? For instance, if the word is “](”, then we can get the correct parenthesization “[]” by two turns and one transformation, with total cost 4.

Input

Input consists of several cases. Every case consists of one word with opening and closing parentheses and square brackets. All the words have even sizes between 2 and 100.

Output

For every case, print the minimum cost of parenthesizing correctly.

Hint

The expected solution has time cost Θ(n3 ) and space cost Θ(n2 ).

Public test cases
  • Input

    ()
    ()[]
    ([](
    )]])
    ])[(
    ](
    )((]([(]
    

    Output

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