# Minimum Add to Make Parentheses Valid

Probelm:-

Given a string `S` of `'('` and `')'` parentheses, we add the minimum number of parentheses ( `'('` or `')'`, and 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.

Sample Input
`()))((`
Sample Output
`4`
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

The given string can be balanced to “((()))(())“, requiring 4 more paranthesis minimum.

Solution:-

#include<stdio.h>
# define max 10000
char stack[max];
int top=-1;
void push()
{
top++;
stack[top]=‘(‘;
}
int main()
{
char str[100000];
int sum=0;
scanf(“%s”,str);
for(int i=0;str[i];i++)
{
if(str[i]==‘(‘)
push();
else
{
if(top==-1)
sum++;
else
top–;

}
}
sum=sum+top+1;
printf(“%d”,sum);
return 0;
}