#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//implementation of stack
//we have declared array as a global variable with limited size.....u can easily modofy it for unknown number of members
char ar[100000];
struct node{
  struct node* link;
  char data;
};
struct node* HEAD=NULL;
//push function
void push(char add){
  struct node* temp=(struct node*)malloc(sizeof(struct node));
  temp->data = add;
  temp->link=HEAD;
  HEAD= temp;
}
void pop(){
  struct node* i=HEAD;
  i=HEAD->link;
  free(HEAD);
  HEAD=i;
  
}
//function to check whether the stack is empty
int empty(){
  if(HEAD==NULL){
    return 1;
  }
  else return 0;
}
//function returning the top of stack
char top(){
  return HEAD->data ;
}
//function to check that opening and closing brackets are matching
int matching(char a , char b){
  if((a=='(')&&(b==')')) return 1;
  else if((a=='[')&&(b==']')) return 1;
  else if((a=='{')&&(b=='}')) return 1;
  else return 0;
}
//function to finally check that string is balanced or not 
int balancing(){
  int n= strlen(ar);
  int i;
  char comp;
  for(i=0;i<n;i++){
    if((ar[i]=='(')||(ar[i]=='[')||(ar[i]=='{')){
      push(ar[i]);
    }
    else if((ar[i]==')')||(ar[i]==']')||(ar[i]=='}')){
      comp=top();
      if(((matching(comp,ar[i]))==0)||(empty()==1)){
        return 0;
      }
      else{
        pop();
      }
    }
  }
  if(empty()==1) return 1;
  else 0;
}
int main(){

  printf("enter the string of brackets\n");
  gets(ar);
  printf("%s\n",ar);
  int k;
  k=balancing();
  if(k==1) printf("balnced");
  else printf("fuck u!!u hav entered unbalanced string!!!!");
}