Minimum Insertions to Balance Parentheses

Problem Statement:

Given a string consisting exclusively of the characters '(' and ')', determine the minimum number of insertion operations required to make the string valid. A string is considered valid if every opening parenthesis has a corresponding closing parenthesis in the correct order. You may insert either '(' or ')' at any position in the string.

The problem can be formalized as follows: Let \( s \) be the input string. As you traverse \( s \), maintain two counters:

• \( open\_needed \): the number of '(' insertions needed when encountering an unmatched ')'.
• \( close\_needed \): the number of ')' needed for unmatched '('.

The total number of insertions required is given by:

\[ \text{answer} = open\_needed + close\_needed \]

For example:

• Input: (() → Output: 1 (one ')' is needed).
• Input: ()) → Output: 1.
• Input: ))( → Output: 3.

Input Format: The input consists of a single line containing a non-empty string of parentheses.

Output Format: Output a single integer denoting the minimum number of insertions required to make the input string valid.

inputFormat

A single line from standard input (stdin) containing a non-empty string composed solely of the characters '(' and ')'.

outputFormat

A single integer printed to standard output (stdout) representing the minimum number of insertions required to balance the parentheses.## sample

()

0