Saturday 10 January 2015

Expression Evaluation using Stacks (PostFix Technique) in C (Makefile)

header.h

long long int solveExpression(char *);
struct Node
{
 int data;
 char op;
 struct Node*next;
};
struct LinkedList
{
 struct Node*start; 
};
struct StackNode
{
 char op;
 struct StackNode*next;
};
struct Node*makeNode(int data,char op);
struct Node*insertAtEnd(struct Node*start, struct Node*newNode);
struct Node*deleteNode(struct Node*start,int data,char op);
void printList(struct Node*start);
struct StackNode*makeStackNode(char op);
struct StackNode*push(struct StackNode*top, struct StackNode*newNode);
struct StackNode*pop(struct StackNode**top);


LinkedList.c

#include"header.h"
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
struct Node*makeNode(int data,char op)
{
 struct Node*newNode;
 newNode=(struct Node*)malloc(sizeof(struct Node*));
 newNode->data=data;
 newNode->op=op;
 newNode->next=NULL;
 return newNode;
}

struct Node*insertAtEnd(struct Node*start, struct Node*newNode)
{
 struct Node*currentNode;
 if(!start)
  return newNode;
 for(currentNode=start;currentNode->next;currentNode=currentNode->next);
 currentNode->next=newNode;
 return start;
}

struct Node*deleteNode(struct Node*start,int data,char op)
{
 struct Node*currentNode,*prevNode=NULL,*temp,*prev;
 for(prevNode=NULL,currentNode=start;;prevNode=currentNode,currentNode=currentNode->next)
 {
  if(currentNode->data==data && currentNode->op==op)
   break;
 }
 if(currentNode==start)
 {
  temp=start;
  start=start->next;
  free(temp);
 }
 else
 {
  prev->next=currentNode->next;
  free(currentNode);
 }
 return start;
}

void printList(struct Node*start)
{
 while(start)
 {
  if((start->op)!='\0')
   printf("%c\n",start->op);
  else
   printf("%d\n",start->data);
  start=start->next;
 }
 printf("\n");
}



LinkedListStack.c

#include"header.h"
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
struct StackNode*makeStackNode(char op)
{
 struct StackNode*newNode;
 newNode=(struct StackNode*)malloc(sizeof(struct StackNode*));
 newNode->op=op;
 newNode->next=NULL;
 return newNode;
}

struct StackNode*push(struct StackNode*top, struct StackNode*newNode)
{
 if(!top)
  return newNode;
 newNode->next=top;
 return newNode;
}

struct StackNode*pop(struct StackNode**top)
{
 struct StackNode*returnNode;
 if(!(*top))
  return NULL;
 returnNode=(*top);
 *top=(*top)->next;
 return returnNode;
}



main.c

#include<string.h>
#include<stdio.h>
#include"header.h"

int main()
{
 char str[100000];
 printf("Enter the expression : ");
 scanf("%[^\n]s",str);
 
 printf("\nAnswer = %lld\n\n",solveExpression(str));
 return 0;
}



solveExpression.c

#include<stdio.h>
#include<stdlib.h>
#include"header.h"
int getPriority(char c)
{
 if(c=='(')
  return -1;
 if(c=='+' || c=='-')
  return 0;
 if(c=='*' || c=='/' || c=='%')
  return 1;
 if(c=='^')
  return 2;
}

struct LinkedList convertToPostfix(struct LinkedList infix)
{
 struct Node*infixNode;
 struct StackNode*top,*temp;
 struct LinkedList postfix;
 top=NULL;
 postfix.start=NULL;
 for(infixNode=infix.start;infixNode;infixNode=infixNode->next)
 {
  if(infixNode->op=='(')
  {
   top=push(top,makeStackNode(infixNode->op));
   continue;
  }
  if(infixNode->op==')')
  {
   while(top && top->op!='(')
   {
    temp=pop(&top);
    postfix.start=insertAtEnd(postfix.start,makeNode(-2147483647,temp->op));
   }
   pop(&top);
   continue; 
  }
  if(infixNode->op=='\0')
  {
   postfix.start=insertAtEnd(postfix.start,makeNode(infixNode->data,infixNode->op));
  }
  else
  {
   if(top==NULL)
    top=push(top,makeStackNode(infixNode->op));
   else
   {
    if(getPriority(infixNode->op)>getPriority(top->op))
    {
     top=push(top,makeStackNode(infixNode->op));
    }
    else
    {
     while(top && getPriority(infixNode->op) <= getPriority(top->op))
     {
      temp=pop(&top);
      postfix.start=insertAtEnd(postfix.start,makeNode(-2147483647,temp->op));
     }
     top=push(top,makeStackNode(infixNode->op));
    }
    
   }
  }
 }
 while(top)
 {
  temp=pop(&top);
  postfix.start=insertAtEnd(postfix.start,makeNode(-2147483647,temp->op));
 }
 return postfix;
}
int operate(int a,int b,char c)
{
 switch(c)
 {
  case '+':
   return a+b;
  case '-':
   return a-b;
  case '*':
   return a*b;
  case '/':
   return a/b;
  case '%':
   return a%b;
  case '^':
   return (a^b);
 }
 return 0;
}
long long int evaluate(struct LinkedList postfix)
{
 int answer;
 struct Node*ptr,*prev1,*prev2;
 while((postfix.start)->next)
 {
  for(ptr=postfix.start,prev1=NULL,prev2=NULL;ptr && ptr->op=='\0';prev1=prev2,prev2=ptr,ptr=ptr->next);
  answer=operate(prev1->data,prev2->data,ptr->op);
  prev1->data=answer;
  
  prev1->next=ptr->next;
  free(prev2);
  free(ptr);
 }
 return (postfix.start)->data;
}
long long int solveExpression(char str[])
{
 struct LinkedList infix,postfix;
 int i,num;
 infix.start=NULL;
 for(i=0;str[i];)
 {
  if(str[i]==' ')
  {
   i++;
   continue;
  }if(str[i]<='9' && str[i]>='0')
  {
   for(num=0;str[i] && str[i]<='9' && str[i]>='0';i++)
    num=num*10+str[i]-'0';
   infix.start=insertAtEnd(infix.start,makeNode(num,'\0'));
  }
  else
  {
   infix.start=insertAtEnd(infix.start,makeNode(-2147483647,str[i]));
   i++;
  }
 }
 postfix=convertToPostfix(infix);
 return evaluate(postfix);
}


Makefile

all: hello
hello: main.o solveExpression.o LinkedList.o LinkedListStack.o
 gcc main.o solveExpression.o LinkedList.o LinkedListStack.o -o hello
main.o: main.c
 gcc -c main.c
evaluateExpression.o: solveExpression.c
 gcc -c solveExpression.c
LinkedList.o: LinkedList.c
 gcc -c LinkedList.c
LinkedListStack.o: LinkedListStack.c
 gcc -c LinkedListStack.c

No comments:

Post a Comment