Play With Brackets

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.

Leave a Reply

Your email address will not be published. Required fields are marked *