check-for-balanced-parentheses-in-an-expression

#import <Foundation/Foundation.h>

@interface Stack:NSObject{

    

}

-(void)push:(NSString *)str;

-(void)pop;

@end

@implementation Stack{

    NSMutableArray *stackArray;

}

-(id)initWithArray:(NSMutableArray*)arr{

    self = [super init];

    if(self){

        stackArray = arr;

    }

    return self;

}

-(id)init{

    return [self initWithArray:[[NSMutableArray alloc] init]];

}

-(BOOL)isEmpty:(NSMutableArray*)arr{

    if(arr.count){

       return NO; 

    }

    else{

      return YES;  

    }

}

-(void)push:(NSString *)str{

    [stackArray addObject:str];

}

-(void)pop{

    

    [stackArray removeLastObject];

}

-(BOOL)isValidSequence:(NSString*)sequence{

    NSDictionary *dict = [[NSDictionary alloc]initWithObjectsAndKeys:@")",@"(",@"}",@"{",@"]",@"[",nil];

    NSArray *arrValues = [dict allValues];

    NSArray *arrKeys = [dict allKeys];

    int length = [sequence length];

    int index = 0;

    while(length>0){

       NSString *str  = [sequence substringWithRange:NSMakeRange(index,1)];

       // NSLog(@"arrk %@\n", arrKeys);

      // NSLog(@"str %@\n", str);

        if([arrKeys containsObject:str]){

           [self push:str];

          // NSLog(@"pushed %@\n", str);

       } 

       

       if(stackArray.count==0){

         return NO;

     } 

        

       NSString *key = [[stackArray lastObject] copy];

      // NSLog(@"key %@\n", key);

        if([arrValues containsObject:str]) {

            if([str isEqualToString:[dict valueForKey:key]]){

                 [self pop]; 

                //

               // NSLog(@"poped %@\n", [dict valueForKey:key]);

            }

            else{

              return NO;

            }

        }

      

       index++;

       length--;

       

    }

     if([self isEmpty:stackArray]==YES){

         return YES;

     }

     return NO;

}

@end    

    

int main(int argc, const char * argv[]){

    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    int t;

    scanf("%i",&t);

    for(int a0 = 0; a0 < t; a0++){

        NSString* expression;

        char* expression_temp = (char *)malloc(512000 * sizeof(char));

        scanf("%s",expression_temp);

        expression = [NSString stringWithFormat:@"%s", expression_temp];

        Stack* stack = [[Stack alloc] initWithArray:[[NSMutableArray alloc]init ]];

        BOOL flag = [stack isValidSequence:expression];

        if(flag){

           // NSLog(@"%@\n",@"YES");

            printf("YES\n");

        }

        else{

            //NSLog(@"%@",@"NO"); 

             printf("NO\n");

        }

    }

    [pool drain];

    return 0;

}