Do you think IIT Guwahati certified course can help you in your career?
Introduction
There are two types of parentheses. Open and close parentheses. In this problem, open parentheses can be like: ‘(, ‘‘{, ‘‘[, ‘ and closed parentheses can be like:‘),’ ‘},’ ‘].’ A well-formed parenthesis string is a balanced parenthesis string. A string of parentheses is called balanced if, for every opening bracket, there is a unique closing bracket. If you don’t have any prior knowledge of balanced parentheses, it’s suggested to look up this blog.
In this article, the problem asks to delete all the balanced parentheses from the string and return the minimum length left.
Given a string, remove all the subsequences which form balanced parentheses and print the remaining characters.
For example:
INPUT : s= “((){()({})”
OUTPUT: “({“
Here, the subsequence consisting of s[1], s[2], s[4], s[5], s[6], s[7], s[8], s[9] is ()()({}). Thus, we remove it and the string left is = ({. Thus the output is this.
INPUT : s= “)()())”
OUTPUT: “))”
Here, the subsequence consisting of s[1], s[2], s[3], s[4] is ()(). Thus, we remove it and the string left is = )). Thus the output is this.
Solution Approach
Thinking about the logic of this problem is straightforward. We have to remove the balanced parentheses. And for this, we need to find balanced parentheses and remove them.
Hint 1:
A valid parenthesis expression has the interesting property that a sub-expression of a valid expression must also be a valid expression. (Not all sub-expression).
For example: Consider a string { [ [ ] { } ] } ( ) ( )
Hint 2:
What if we simply remove the matching pair of parentheses whenever we come across them in the expression? It would further shorten the expression.
For example:
{ { } { ( ) } //remove matching pair 1
|_|
{ _ _ { ( ) } //remove matching pair 2
|_|
{ _ _ { _ _ } //remove matching pair 3
|____|
This is exactly what we will do. We keep pushing the characters of the string into a stack and at the time when the top element of the stack is an opening bracket and the current element is a closing bracket, we pop the top element of the stack as these both are forming a balanced parenthesis. Otherwise, keep pushing elements into the stack.
Steps are :
Input the string and call the function remove_parenthesis() with the string as a parameter.
In the function remove_parenthesis():
Declare a stack of characters.
Start iterating from i=0 to i<s.length() of the string.
If the current character is an opening bracket, i.e., s[i] ==’(,’ or ‘{’ or ‘[,’ push it into the stack.
Else if s[i]==’),’ or ‘}’ or ‘].’
If the stack is empty, push it into the stack.
Otherwise, if the top element of the stack is an opening bracket, pop it from the stack and move to the next i. Otherwise, push s[i] into the stack.
At this stage, the stack contains the left-out characters. So, just declare an answer string, then add the elements of the stack into it.
Since the stack contains elements in reverse order of their occurrence, we need to reverse the answer string. So, reverse the answer string.
Return the answer string.
Print the returned string.
C++ implementation
Below is the C++ implementation of the above idea.
#include<bits/stdc++.h>
using namespace std;
string remove_parenthesis(string s){
stack<char>stk; // Declare a stack of characters
//Start iterating from i=0 to i<s.length() of the string.
for(int i=0;i<s.length();i++){
// If the stack is empty, push the current character into it
if(stk.empty()){
stk.push(s[i]);
}
else{
//If the current character is an opening bracket, i.e;
//s[i] ==’(’, or ‘{’ or ‘[’, push it into the stack.
if(s[i]=='{' || s[i]=='(' || s[i]=='['){
stk.push(s[i]);
}
//if the top element of the stack is an opening bracket, pop it
//from the stack and move to the next i.
else if(stk.top()=='{' || stk.top()=='(' || stk.top()=='['){
stk.pop();
}
//else push it into the stack
else{
stk.push(s[i]);
}
}
}
// At this stage the stack contains the left out characters. So, just declare
// an answer string the add the elements of the stack into it.
string ans;
while(!stk.empty()){
ans+=(stk.top());
stk.pop();
}
// Since, the stack contains elements in reverse order of their occurence,
// we need to reverse the answer string
reverse(ans.begin(),ans.end());
// Return the answer string
return ans;
}
int main(){
string s; // Input the string
cin>>s;
string ans = remove_parenthesis(s);
cout<<ans<<endl; // Print the answer string
};
You can also try this code with Online C++ Compiler
A stack is an abstract data type that serves as a collection of elements and has two primary operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that has not yet been removed.
What data structure can be used to check if the syntax has balanced parentheses?
Stack comes in handy to check if the syntax has balanced parentheses.
What are balanced parentheses?
A string of parentheses is intuitively balanced if each left parenthesis has a matching right parenthesis and the matched pairs are well nested.
What is stack pop ()?
Stack pop() removes the most recently added element that has not yet been removed.
Conclusion
In this article, we’ve discussed the problem minimize the length of a given string by removing subsequences forming valid parenthesis.
84+ registered