Check the given Arithmetic expression is properly balanced

^^^

Check the given Arithmetic expression is properly balanced or not. {[a Times b - (b + c)]^* [sin(x - y)]}-(x - y) Write the algorithm for the expression and also write a program for it.

Solution

To determine, whether the arithmetic expression is properly balanced or not we must check that a right counter part ‘)’ or ‘]’ or ‘}’ exist for each left ‘(’ or ‘{‘ or ‘[‘ in a proper order. To do this we use a Stack and start search from the first character to the last character for the given expression. Whenever we encountered a LEFT - BRACKETS ( left parentheses ‘(’ or left braces‘{‘ or left bracket ‘[‘ ) , we push onto the Stack. Whenever we encountered a RIGHT - BRACKETS ( right parentheses ‘)’ or right bracket ‘]’ or right braces ‘}’ ) , we pop the top symbol from the Stack and check to see whether the encountered RIGHT - BRACKET and Stack top LEFT - BRACKET are same type or not?. We continue if they are same type, otherwise we stop the process.

                The expression has properly balanced, if the Stack is empty by the time we get to the end of the expression and all pairs of matched BRACKETS were of the same type. Otherwise, the BRACKETS are not balanced properly.

Algorithm

Step1.   Matching        True

Step2.   Clear the Stack S.

Step3.   Read symbol as a first character from the input string.

Step4.   While (symbol is not a end of input string & Matching is True ) do

                    {

                                If ( symbol is ‘ ( ‘   or    symbol is ‘ [ ‘   or   symbol is ‘ { ‘ )

                                                Push( S ,symbol )

                                Else if ( symbol is ‘ )‘   or    symbol is ‘ ] ‘   or   symbol is ‘ } ‘ )

                                    {

                                                If ( Is¬¬_Empty(S) )

                                                    {

                                                    Matching      False

                                                    Write “More Right Brackets than from Left Brackets“ && Return

                                                     }

                                                Else

                                                    {

                                                                topsymb          Pop(S)

                                                                If ( ! Equal_Type( topsymb , symbol ) )

                                                                    {

                                                                                Matching         False

                                                                                Write “ Miss matched Brackets “ &&   Return

                                                                    }

                                                    }

                                    }

                                symbol               Next character in the input string.

                    }

Step5.   If ( Is_Empty(S) )

                                Write “ Brackets are Properly Balanced”

       Program:

#include<stdio.h>

#define MAX 20

struct stack

{

       char item[MAX];

       int top;

}s;

typedef struct stack ST;

int leftbrkt(char);

int rightbrkt(char);

int is_empty(ST *);

void stack_clear(ST *);

int equal_type(char,char);

void push(ST *,char);

char pop(ST *);

leftbrkt(char x)

{

        return( ( ( x= =\'(\' ) || ( x= =\'[\' ) || ( x= =\'{\' ) ) ? 1 : 0 );

} The Return statement contains Ternary Operator. First it checks whether the expression ( ( x= =\'(\' ) || ( x= =\'[\' ) || ( x= =\'{\' )   ) is true or not?. If true it returns 1, Otherwise it returns 0.

rightbrkt(char x)

{

       return( ( ( x= =\')\' ) || ( x= =\']\' ) || ( x= =\'}\' ) ) ? 1 : 0 );

}

equal_type(char ch, char top_ch)

{

    switch(ch)

      {

                case \')\' : return( ( top_ch = = \'(\' ) ? 1 : 0 );

                case \']\' : return( ( top_ch = = \'[\' ) ? 1 : 0 );

                case \'}\' : return( ( top_ch = = \'{\' ) ? 1 : 0 );

      }

}            First ch gets any one of the Right Brackets character and control goes to the correspondent case value area. Later top_ch is compare with ch correspondent Left Bracket and return value 1 if both ch & top_ch are same type, otherwise return 0 .

int is_empty(ST *ts)

   {

        return( (ts->top == -1) ? 1: 0);

   }

void stack_clear(ST *ts)

   {

         ts->top =-1;

   }

void push(ST *ts,char x)

{

         ts->item[++(ts->top)] =x;

}

char pop(ST *ts)

{

          return ( ts->item[(ts->top)--] );

}

main()

{

     int i,matched = 1;         char exp_str[30],c,t;       ST s;

     clrscr();

     stack_clear(&s);

     printf(\"Enter The Expression to Check Balance : \ \");

     scanf(\"%s\",exp_str);

     for(i=0;( (c=exp_str[i]) !=\'\\0\' );i++)

        {

                if( (leftbrkt(c)) == 1)

                   push(&s,c);

                else

                    {

                       if((rightbrkt(c) ) == 1 )

                                {

                                   if(is_empty(&s))

                                     {

                                                matched =0;

                                                printf(\"More Right Brackets than Left Brackets \ \");

                                                getch();        exit(0);

                                     }

                                   else

                                     {

                                                t = pop(&s);

                                                if( ! equal_type(c,t) )

                                                {

                                                     matched =0;

                                                     printf(\" Miss matched Brackets \");

                                                     getch();          exit(0);

                                                }

                                     }

                                }

                    }

         }

       if(is_empty(&s) && matched )

                   printf(\"The Brackets are Properly Balanced\");

       else

                   printf(\"More Left Brackets than Right Brackets\");

       getch();

}