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.