balanced brackets

 Problem:-

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {},and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

It contains no unmatched brackets.
The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.
Given n strings of brackets, determine whether each sequence of 
brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

INPUT:

The first line contains a single integer n, the number of strings. 

Each of the next n lines contains a single string s, a sequence of brackets.

CONSTRAINTS:

1<=n<=10^3
1<=|s|<=10^3, where  is the length of the sequence.
All chracters in the sequences ? { {, }, (, ), [, ] }.

OUTPUT:

For each string, return YES or NO.
 

Sample Input

3
{[()]}
{[(])}
{{[[(())]]}}

Sample Output

YES
NO
YES

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

1.The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.

2.The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).

3.The string {{[[(())]]}} meets both criteria for being a balanced string, so we print YES on a new line.

Code:-

#include<stdio.h>

#include<stdlib.h>

struct stack

{

int top;

int capacity;

char *array;

};

struct stack* creatstack(int cap)

{

struct stack *stack;

stack=(struct stack*)malloc(sizeof(struct stack));

stack->top=-1;

stack->capacity=cap;

stack->array=(char *)malloc(sizeof(char)*stack->capacity);

return(stack);

}

int isfull(struct stack* stack)

{

if(stack->top==stack->capacity-1)

return(0);

else

return(1);

}

int isempty(struct stack *stack)

{

if(stack->top==-1)

return(0);

else

return(1);

}

void push(struct stack *stack,char item)

{

if(isfull(stack))

{

stack->top++;

stack->array[stack->top]=item;

}

}

char pop(struct stack *stack)

{

char item;

if(isempty(stack))

{

item=stack->array[stack->top];

stack->top--;

return(item);

}

else

return('a');

}

int main()

{

int i,flag=0,n,r,j;

char s[1000],ch;

struct stack* stack;

stack=creatstack(1000);

scanf("%d",&n);

for(j=1;j<=n;j++)

{

scanf("%s",s);

for(i=0;s[i];i++)

{

if(s[i]=='('||s[i]=='{'||s[i]=='[')

push(stack,s[i]);

if(s[i]==')'||s[i]=='}'||s[i]==']')

{

ch=pop(stack);

if(s[i]==')')

{

if(ch!='(')

{

printf("NO\n");

flag=1;

break;

}

}

if(s[i]=='}')

{

if(ch!='{')

{

printf("NO\n");

flag=1;

break;

}

}

if(s[i]==']')

{

if(ch!='[')

{

printf("NO\n");

flag=1;

break;

}

}

}

}

r=isempty(stack);

if(r==0&&flag==0)

printf("YES\n");

else

{

if(flag==0)

printf("NO\n");

}

flag=0;

while(isempty(stack))

pop(stack);

}

return 0;

}