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;

}