Stack: Remove outer most redundant parenthesis

Problem Statement:

You are given a string “S”. You need to print the string obtained by removing the outermost parenthesis.

Example

Input: S = “(()())(())()”
Output: ()()()

Solution

In the solution, we will use stack,

We will take 2 variables, one stack and one resultant string.

When we encounter “(“, we will check if the stack size is > 0, then we will add “(” into the result string and into the stack. Else we will just push into the stack.

Similarly when we encounter “)”, if the sack size is greater than 0, then add it into the stack and then pop an element from the stack.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

string remove_outer_parentheses(string S) 
{
    string result="";
    stack<char> st;
    for(auto ch : S){
        if(ch=='('){
            if(st.size()>0){
                result+=ch;
            }
            st.push(ch);
        }
        else{
            if(st.size()>1){
                result+=ch;
            }
            st.pop();
        }
    }
    return result;
}
int main()
{ 
    string s = "(()())(())";

    cout<<"The string after removing outer parenthesis is "<<remove_outer_parentheses(s)<<endl;

    return 0;

}

Output:

The string after removing outer parenthesis is ()()()