Sunday, 31 May 2015

Check For Balanced Expression in an expression


Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”  

// a function to check if two given characters are a matching pair
bool isMatchingPair( char chr1 , char chr2   )
{
    if( chr1 == '(' && chr2 == ')')
        return 1 ;
    else if( chr1 == '{' && chr2 == '}')
        return 1 ;
    else if( chr1 == '[' && chr2 == ']')
        return 1 ;
     else
        return 0 ;
       
       
}

bool arePraenthesisBalanced (char exp[])
{
    int i = 0 ;
   
    // an empty character stack  to be made up of linked list
    struct sNode* stack = NULL;
   
    //while we dont approach the null character of the string
        while( exp[i])
        {
            // if exp[i] is a starting charcter push it
            if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
                push(&stack, exp[i]);
          
           //if the exp[i] is an ending parenthesis , pop from stack and check whether it matches as the type of starting parenthesis exp[i]
            if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
            {
                //if the stack is NULL , return false  as  this is an extra invalid parentheis
                if(stack == NULL)
                {
                    return 0 ;
                }
                 // pop the character and check if it is  not of the type of exp[i] , return false
                 else if(!(isMatchingPair(pop(&stack) , exp[i])))
                    return 0 ;
               
            }
            ++i;
          
        }
       
        //if there is something left in stack , means we found an unmatched single parenthesis type
        // return false
        if(stack  == NULL )
            return true ; //balanced
          else
            return false; //unbalanced
         
}

No comments:

Post a Comment