Stack Data Structure

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.


Given a string of parentheses, it contains between 1 and 50 characters, inclusive.


Print the minimum number of parentheses that need to be inserted to make the input string into a well formed string.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1