C program to check a mathematical expression for correctness in terms of brackets, using Stack

Posted: April 1, 2012 in Lab 7
/* C program to check a mathematical expression for
 correctness in terms of brackets, using Stack
  Written by- Shivam Rana */
#include<stdio.h>
#include<stdlib.h>
 
struct sNode
{
   char data;
   struct sNode *next;
};
 
void push(struct sNode** top_ref, int new_data);
 
int pop(struct sNode** top_ref);
 

int isMatchingPair(char character1, char character2)
{
   if(character1 == '(' && character2 == ')')
     return 1;
   else if(character1 == '{' && character2 == '}')
     return 1;
   else if(character1 == '[' && character2 == ']')
     return 1;
   else
     return 0;
}
 
int areParenthesisBalanced(char exp[])
{
   int i = 0;

   struct sNode *stack = NULL;
 
  
   while(exp[i])
   {
      if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
        push(&stack, exp[i]);

      if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
      {
 
          
         if(stack == NULL)
           return 0;
 

         else if ( !isMatchingPair(pop(&stack), exp[i]) )
           return 0;
      }
      i++;
   }
 
  
   if(stack == NULL)
     return 1; /*balanced*/
   else
     return 0;  /*not balanced*/
}
 

int main()
{
  char exp[100];
	printf("Enter expression\n");
	scanf("%s",exp);
  if(areParenthesisBalanced(exp))
    printf("\nBalanced ");
  else
    printf("\nNot Balanced ");  \
  getchar();
}   
 

void push(struct sNode** top_ref, int new_data)
{

  struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));
 
  if(new_node == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }          
 

  new_node->data  = new_data;
 
  
  new_node->next = (*top_ref); 
 
 
  (*top_ref)    = new_node;
}
 

int pop(struct sNode** top_ref)
{
  char res;
  struct sNode *top;
 
  /*If stack is empty then error */
  if(*top_ref == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
  }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s