Minimum Add to Make Parentheses Valid

Rajnish Tripathi 23:16

 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;
}



Tags: