Last Updated on December 13, 2022 by Prepbytes
Concepts Used
Stack
Difficulty Level
Easy.
Problem Statement :
Rashid is given a set of open and closed brackets of each type such as [ , ], ( , ) and { , } by his teacher and he is asked to construct a valid set of brackets from the given set. A set is said to be valid if
1.Open brackets must be closed by the same type of closing brackets.
2.Open brackets must be closed in the correct order.
You have to determine that the set constructed by Rashid is valid or not.
See original problem statement here
Example:
Input
3
{([])}
()
([]
Output
Valid
Valid
Not Valid
In the first and second test case each opening bracket
is closed by the corresponding same type of closing bracket.
In the third test case, there is no closing bracket of '(',
so the string is not valid.Explanation:
Using stack:
When any open symbol i.e, (, {, [ is encountered, it will be pushed in the stack.
If any close symbol i.e, ), }, ] is encountered, any of the three can happen
The TOS (Top Of Stack) is checked, if the encountered close symbol matches with its open symbol, then open symbol which is at TOS is popped out.(OR)
The TOS (Top Of Stack) is checked, if the encountered close symbol does not match with its open symbol, then -1 is returned as there is no matching symbol. (OR)
The TOS (Top Of Stack) is checked,if the stack is empty, then -1 is returned as there is no open symbol in the stack.
Solutions:
#include <stdio.h>
int closingbracket(char c)
{
if(c=='}'||c==')'||c==']')
return 1;
return 0;
}
int isvalid(char s[],int len)
{
int st[len];
int top=-1;
for(int i=0;i<len;i++)
{
if(top==-1)
{
if(closingbracket(s[i]))
return 0;
st[++top]=s[i];
}
else
{
if(!closingbracket(s[i]))
st[++top]=s[i];
else
{
if(s[i]==']')
if(st[top]!='[')return 0;
if(s[i]==')')
if(st[top]!='(')return 0;
if(s[i]=='}')
if(st[top]!='{')return 0;
top--;
}
}
}
if(top!=-1)
return 0;
return 1;
}
int main()
{
// write your code here
int t;scanf("%d",&t);
while(t--)
{
char s[1001];
scanf("%s",s);
int l=strlen(s);
if(isvalid(s,l))
printf("Valid\n");
else
printf("Not Valid\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
bool closingbracket(char c)
{
if(c=='}'||c==')'||c==']')
return true;
return false;
}
bool isvalid(string s)
{
int l=s.length();
stack<char>st;
for(int i=0;i<l;i++)
{
if(st.empty())
{
if(closingbracket(s[i]))
return false;
st.push(s[i]);
}
else
{
if(!closingbracket(s[i]))
{
st.push(s[i]);
}
else
{
if(s[i]=='}')
if(st.top()!='{')return false;
if(s[i]==')')
if(st.top()!='(')return false;
if(s[i]==']')
if(st.top()!='[')return false;
st.pop();
}
}
}
if(!st.empty())return false;
return true;
}
int main()
{
//write your code here
int t;cin>>t;
while(t--)
{
string s;cin>>s;
if(isvalid(s))
cout<<"Valid\n";
else
cout<<"Not Valid\n";
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static boolean findbalancedbrackets(String str)
{
int N = str.length();
Stack<Character> st = new Stack<Character>();
for(int i=0;i<N;i++)
{
if(str.charAt(i)=='{' || str.charAt(i)=='[' || str.charAt(i)=='(')
st.push(str.charAt(i));
else
{
if(st.isEmpty())
return false;
char x = st.peek();
st.pop();
if(str.charAt(i) == ')')
if(x == '[' || x == '{')
return false;
if(str.charAt(i) == '}')
if(x == '[' || x == '(')
return false;
if(str.charAt(i) == ']')
if(x == '(' || x == '{')
return false;
}
}
if(!st.isEmpty())
return false;
else
return true;
}
public static void main(String args[]) throws IOException {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
sc.nextLine();
while(t-- >0){
String str=sc.nextLine();
if(findbalancedbrackets(str))
System.out.println("Valid");
else
System.out.println("Not Valid");
}
}
}
[forminator_quiz id="2312"]
This article tried to discuss the concept of stack. Hope this blog helps you understand stack. To practice more problems you can check out MYCODE | Competitive Programming.