Minimum Additions to Make Valid Parentheses

You are given a string s consisting only of characters '(' and ')'. The task is to determine the minimum number of parentheses you must add to make the string valid. A valid string is defined as a string in which every open parenthesis has a corresponding closing parenthesis and the pairs of brackets are properly nested.

In other words, if we denote an open parenthesis by \( ( \) and a closing parenthesis by \( ) \), the string is valid if it can be transformed into a well-formed sequence. You are allowed to insert parentheses at any positions in the string.

Example:

• For s = "(()))", the answer is 1 since one additional opening parenthesis at the beginning makes it valid.
• For s = "((())", the answer is 1 since one additional closing parenthesis at the end makes it valid.
• For s = ")()())", the answer is 2.

inputFormat

The input consists of a single line containing the string s composed exclusively of the characters '(' and ')'.

outputFormat

Output a single integer, which is the minimum number of parentheses that need to be added to make the string valid.

()()

0