Insert Parentheses
Milhouse need to solve a school task by tomorrow and needs your help. Here is the task:
Given a string of parentheses, you must turn it into a well formed string by inserting as few parentheses as possible, at any position (you cannot delete or change any of the existing parentheses). 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) is a well formed string.
If s and t are well formed strings, their concatenation st is a well formed string.
As examples, "(()())", "" and "(())()" are well formed strings and "())(", "()(" and ")" are malformed strings.
Input
Given a string of parentheses, it contains between 1 and 50 characters, inclusive.
Output
Print the minimum number of parentheses that need to be inserted to make the input string into a well formed string.