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 in data structures and algorithms, 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 
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



						 
import java.util.*;
  import java.io.*;
  public class Main {
   static boolean findbalancedbrackets(String str) 
   {
        int N = str.length();

         Stack st = new Stack();
        for(int i=0;i0){

        String str=sc.nextLine();
        if(findbalancedbrackets(str))
              System.out.println("Valid");
        else 
          System.out.println("Not Valid");
        }

    }
  }
#include 
using namespace std;
bool closingbracket(char c)
{
  if(c=='}'||c==')'||c==']')
  return true;
  return false;
}
bool isvalid(string s)
{
  int l=s.length();
  stackst;
  for(int i=0;i>t;
  while(t--)
  {
    string s;cin>>s;
    if(isvalid(s))
    cout<<"Valid\n";
    else
    cout<<"Not Valid\n";
  }
  return 0;
}

Previous post Stack Challenge
Next post REVERSE LINK LIST

Leave a Reply

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