Validity Checking on Expression

 Algorithm : Checking validity of an Algebric Expression

Let us consider an algebraic expression,A,which contains operands, operators, ’(‘ , ’)’ , 
‘{‘ , ‘}’ , ‘[‘ , ‘]’.This algorithm checks the validity of the expression in algebraic sence,
 i.e for every ‘(‘ there will be a matching ‘)’, for every ‘{‘ there will be a matching ‘}’ 
and for every ‘[‘ there will be a matching ‘]’.

Valid_expression(A[1..N])
{
 
 Let us consider a stack ‘S’ which contains the symbols read from A.
 Push and Pop operation are done on the top of the stack.
 Add ‘$’ to the end of A.
 
 i=0;
 while(A[i]≠'$')                    //until the expression finishes
 {
   if(A[i]='(' or A[i]='{' or A[i]='[')
   {
    push(A[i])
   }
   else if(A[i]=')')
   {
     if(top=-1)                    //checks if the stack is empty
      {
       Print  "Expression invalid"
       exit
      }
     else
      {
       item=pop()
       if(item≠'(')            //checks if there is no matching ‘)’ 
	  {
	   Print  "Expression invalid"
	   exit
	  }
      }
   }

else if(A[i]='}')
    {
     if(top=-1)                     //checks if the stack is empty
      {
       Print  "Expression invalid"
	  exit
      }
     else
      {
       item=pop()
       if(item≠'{')            //checks if there is no matching ‘)’
	{
	 Print  "Expression invalid"
	 exit
	}
      }
    }

    

else if(A[i]=']')
    {
     if(top=-1)                     //checks if the stack is empty
     {
       Print  "Expression invalid"
       exit    
     }
     else
     {
       item=pop()
       if(item≠'[')             //checks if there is no matching ‘)’
	{
	 Print  "Expression invalid"
	 exit
	}
     }
    }
i=i+1
}
  if(top=-1)              //checks if all pairs of bracket is found
  {
   Print  "Valid expression"
  }
  else
  {
   Print  "Expression invalid"
  }
}


 C program For Validity Checking on Expression

Source Code:

 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 #include<string.h>

int top=-1;
char a[10];

void push(char item)
{
 
 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     a[top]=item;
   }
}

char pop()
{
  char item;
  if(top==-1)
   {
     printf("\nStack Underflow");
     item=-1;
   }
  else
   {
     item=a[top];
     top=top-1;
   }
  return item;
}

main()
{
char item,e[15];
int i;
 printf("\nEnter an expression:");
gets(e);
strcat(e,"$");
i=0;
while(e[i]!='$')
{
   if(e[i]=='(' || e[i]=='{' || e[i]=='[')
   {
    push(e[i]);
   }
   else if(e[i]==')')
   {
     if(top==-1)
      {
       printf("\nExpression invalid");
       exit(0);
      }
     else
      {
       item=pop();
       if(item!='(')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
       }
    }

    else if(e[i]=='}')
    {
     if(top==-1)
      {
       printf("\nExpression invalid");
	exit(0);
      }
     else
      {
       item=pop();
       if(item!='{')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
      }
    }

    else if(e[i]==']')
    {
     if(top==-1)
     {
       printf("\nExpression invalid");
       exit(0);
     }
     else
     {
       item=pop();
       if(item!='[')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
     }
    }
i=i+1;
}
  if(top==-1)
  {
   printf("\n....::.Valid expression.::....");
  }
  else
  {
   printf("\nExpression invalid");
  }
  getch();
}



 OUTPUT 1:
Enter an expression:[{a+f-(b-c}]

Expression invalid.
-----------------------------------
 OUTPUT 2:

Enter an expression:{(a+b)*(c-d)}

....::.Valid expression.::....