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
