# Dynamic programming O(n^3)

# Correcting Parenthesization

Given a string of parentheses, we must turn it into a well formed string by changing as few characters as possible (we cannot delete or insert characters).

There are three kinds of parentheses: regular (), brackets [] and curly brackets {}. Each pair has an opening ('(', '[' and '{' respectively) and a closing (')', ']' and '}') character.

A well formed string of parentheses is defined by the following rules:

- The empty string is well formed.
- If
**s**is a well formed string, (**s**), [**s**] and {**s**} are well formed strings. - If
**s**and**t**are well formed strings, the concatenation**st**is a well formed string.

As examples, "([{}])", "" and "(){}[]" are well formed strings and "([}]", "([)]" and "{" are malformed strings.

For the given string of parentheses find the minimum number of characters that need to be changed to make it into a well formed string.

** Input**

Each line contains the string with even number of symbols '(', ')', '[', ']', '{', '}'. The length of each line is no more than **50**.

** Output**

For each input string print in a separate line the minimum number of characters that need to be changed to make it into a well formed string.

]()[((() ([)] ([{}[]

3 2 1