# Minimum Add to Make Parentheses Valid

# Given a string S consisting only of ( and ) parentheses, we add the minimum number of parentheses ( or ) in any positions so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

- It is the empty string, or
- It can be written as
**AB** (**A** concatenated with **B**), where **A** and **B** are valid strings, or
- It can be written as
**(A)**, where **A** is a valid string.

Given a parentheses string, return the **minimum number of parentheses we must add to make the resulting string valid**.

**Input:**

An invalid/valid parenthesis string.

**Output:**

Minimum number of brackets to be added so that it becomes valid.

**Example:**

Example 1:
Input:
"())"
Output:
Minimum number of brackets to be added is 1
(valid parenthesis would be "(())"
Example 2:
Input:
"((("
Output:
Minimum number of brackets to be added is 3
(valid parenthesis would be "((()))"
Example 3:
Input:
"()"
Output:
Minimum number of brackets to be added is 0
(Already a valid parenthesis)
Example 4:
Input:
"()))(("
Output:
Minimum number of brackets to be added is 4
(valid parenthesis would be "()()()(())"

Let's discuss the last example which pretty much covers the other cases as well. The thing to note is we can only add, we can't delete. So, we need to insert the corresponding bracket whenever there is a violation. We can track the violation using stack similar way we check for valid parenthesis.

The algorithm will be like follow,

stack<char> st;count=0;Count gives the final result

Now let's execute for our example,

C++ Implementation:Output: