Q:

# 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

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,

1. Create a stack to store characters, stack<char> st;
2. Initialize the count of minimum numbers to be added, count=0;
3. ```for i=0 to s.length()-1
if(s[i]  is  opening bracket )
push to stack
else{ //s[i] is closing bracket
if stack is empty{
increment count as its a violation
continue;
}
else if(s[i] is closing bracket but the stack top is not opening bracket){
// it's a violation and increment count;
st.pop();
}
}
```
4. If there is still some opening brackets left in the stack they needs to be paired as well, so
```count=count+stack size;
```
Stack size may be zero too
Count gives the final result

Now let's execute for our example,

```String s="()))(("
Initially count=0
Stack is empty

i=0
s[i]=('
push to stack
stack
--------
(
--------
Count=0

i=1
s[i]=')'
s[i] correctly pairs with top of stack
pop from stack
stack is empty now
--------

--------
Count=0

i=2
s[i]=')'
stack is empty, nothing to pair,
it's a violation and we need to add '(' here
--------

--------
increment count
Count=1

i=3
s[i]=')'
stack is empty, nothing to pair,
it's a violation again and we need to add '(' here
--------

--------
increment count
Count=2

i=4
s[i]=('
push to stack
stack
--------
(
--------
Count=2

i=5
s[i]=('
push to stack
stack
--------
(
--------
(
--------
Count=2

That's end the loop

Out of the loop stack is not empty
and we need to add two closing brackets
to pair up those remaining open brackets

Hence, count = count + stack size = 4

That's the final result
```

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

{
stack<char> st;
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(')
st.push(s[i]);
else {
if (st.empty()) {
count++;
continue;
}

else if (s[i] == ')' && st.top() != '(')
count++;

st.pop();
}
}

count += st.size();

return count;
}

int main()
{
string s;
cout << "Enter the parenthesis string\n";
cin >> s;

return 0;
}
``````

Output:

```RUN 1:
Enter the parenthesis string
(())))((

RUN 2:
Enter the parenthesis string
()(((((((((()