Balance Parentheses

Given a string consisting solely of the characters '(' and ')', determine the minimum number of parentheses that must be added to the string in order to make it valid.

A valid string is one where each opening parenthesis '(' has a corresponding closing parenthesis ')' and vice versa. In other words, if we define the balance at any position in the string as \(\text{balance} = \#( '(' ) - \#( ')' )\), then the string is valid if the balance is zero at the end and never becomes negative along the way.

Example:

• For the input ()), the output is 1 since one opening parenthesis needs to be added.
• For the input (((), the output is 3.

inputFormat

The input consists of a single line containing a string comprised solely of the characters '(' and ')'.

outputFormat

Output a single integer representing the minimum number of parentheses that need to be added to the input string to make it valid.

())

1