Posts
definition:
infix: an arithmetic expression is called infix, when it has the operators between the operands.
example: a+b is a infix expression.
postfix: When the operators appear after the operands, then it is called postfix. postfix is actually meant for machines. an example of postfix is: ab+
prefix: when the operators appear before the operands, it is called prefix. prefix is also a machine oriented expression. an example of prefix is: +ab
It is a very classic task to transform infix to postfix and postfix evaluation. We will write functions for both of them and also we will use the driver program to show whether it works or not.
Infix to postfix conversion:
This can be done using stacks. Here is a brief of the algorithm:
We read one character at a time from the infix expression.
If this is a operand then we send it to the output string. The output string is supposed to be the postfix expression at the end.
If it is an operator, we store it to a stack using the following rules:
(1) if the stack is empty, just store the operator in it.
(2) it the stack contains operators, check the precedence of the top operator. If the top-most operator has more precedence, it gets popped and the the new operator gets stored after that. The popped operator is stored in the output string.
Otherwise, the new operator gets stored without any pop.
(3) when one encounters "(" one stores it. But on encountering ")", one pops operators and stores them in the output string until one finds "(" in the stack. When one finds the "(", its just popped and is not stored.
using these rules, one continues to create the output string. Once one has completed parsing the infix expression, he/she pops all the values from the stack and stores them in the output string.
This final output string will be the required postfix expression.
(1) the precedence function: This is the easiest part of this program. Here is the code for a precedence function below.
int precedence(char c)
{
if(c=="-")
{return 0;}
if(c=="+")
{return 1;}
if(c=="*")
{return 2;}
if(c=="/")
{return 3;}
if(c=="^")
{return 4;}
if(c=="(" || c==")")
{return 5;}
}
(2) postfix converter function:
char *postfix_converter(char *string,int length)
{ char s[100]="\0"; int i; stack operators;
for(i=0;i<length;i++)
{
char c;
c=string[i];
if(c==plus || c==subtract || c==multi || c==divi || c==power || c==left)
{
if(top==NULL)
{
push(c);
}
else
{
if(precedence(c)>precedence(peek()) || peek()==left)
{
push(c);
}
else
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
push(c);
}
}
}
else
{
if(c==right)
{
while(peek()!=left)
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
}
pop();
}
else
{
char r[2]="\0";
r[0]=c;
strcat(s,r);
// printf("%s\n",s);
// char j=peek();
// printf("%c",j);
}
}
if(i==(length-1))
{// printf("%d",count);
while(count>0)
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
// printf("lool");
}
}
// printf("%d\n",count);
// printf("%s\n",s);
}
//printf("%d\n",pop());
printf("%s",s);
}
(3) Now at last, if you want the readymade program, here it is:
The complete program is the following:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100
int count=0;
typedef struct node{
char value;
struct stack *next;
struct stack *prev;
}stack;
stack *bottom=NULL;
stack *top=NULL;
stack *createnode(char a)
{
stack *newstack;
newstack=(stack*)calloc(1,sizeof(stack));
newstack->value=a;
newstack->prev=NULL;
newstack->next=NULL;
return newstack;
}
int isempty()
{
if(count==0)
{return 1;}
else
{return 0;}
}
int isfull()
{
if(count==SIZE)
{return 1;}
else
{return 0;}
}
void push(char a)
{ if(isfull()==1)
{
printf("overflow condition: stack full");
}
else
{count+=1;
stack *newstack = createnode(a);
if(bottom==NULL)
{
bottom=newstack;
top=bottom;
}
else
{
top->next=newstack;
newstack->prev=top;
top=newstack;
}
}
}
char peek()
{
return top->value;
}
char pop()
{ if(isempty()==1)
{
printf("underflow condition:empty stack");
}
else
{if(count==1)
{ char c;
c=top->value;
top=NULL;
bottom=NULL;
count=count-1;
return c;
}
else
{char c;
c=top->value;
top=top->prev;
top->next=NULL;
count=count-1;
return c;
}
}
}
char plus=43;
char multi=42;
char divi=47;
char power=94;
char left=40;
char right=41;
char subtract=45;
int precedence(char c)
{ int precide=0;
if(c==subtract)
{precide+=0;}
if(c==plus)
{precide+=1;}
if(c==multi)
{precide+=2;}
if(c==divi)
{precide+=3;}
if(c==power)
{precide+=4;}
if(c==left || c==right)
{precide+=5;}
return precide;
precide=0;
}
char *postfix_converter(char *string,int length)
{ char s[100]="\0"; int i; stack operators;
for(i=0;i<length;i++)
{
char c;
c=string[i];
if(c==plus || c==subtract || c==multi || c==divi || c==power || c==left)
{
if(top==NULL)
{
push(c);
}
else
{
if(precedence(c)>precedence(peek()) || peek()==left)
{
push(c);
}
else
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
push(c);
}
}
}
else
{
if(c==right)
{
while(peek()!=left)
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
}
pop();
}
else
{
char r[2]="\0";
r[0]=c;
strcat(s,r);
// printf("%s\n",s);
// char j=peek();
// printf("%c",j);
}
}
if(i==(length-1))
{// printf("%d",count);
while(count>0)
{
char r[2]="\0";
r[0]=pop();
strcat(s,r);
// printf("lool");
}
}
// printf("%d\n",count);
// printf("%s\n",s);
}
//printf("%d\n",pop());
printf("%s",s);
}
// driver code , the main function
int main(void)
{ char inversion[200];
printf("give the infix expression\n");
scanf("%s",&inversion);
int longer=strlen(inversion);
postfix_converter(inversion,longer);
return 0;
}
input: (2+3)^3-4+9
output:
Success #stdin #stdout 0s 9432KB
give the infix expression
23+3^49+-
input: (2+3)^3
output:
Success #stdin #stdout 0s 9432KBgive the infix expression
23+3^
input:(3/3)^3+3-3
output:
Success #stdin #stdout 0s 9432KBgive the infix expression
33/3^3+3-
For more details, visit here https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
(4) postfix evaluation program:
For evaluation of postfix expression, the algorithm is easy:
(1) parse through the expression character by character.
(2) if a character is operand then push it to stack.
else if it is an operator, pop two operands from the stack and then perform the operation as
new_item=popped_2 operator popped_1
push this new_item back to stack.
(3) at the end of the loop of step 2, pop the stack once as you must only have the result left in the stack. print it. You are done. voila!!
Here is the function named as postfix_evaluation!
(5) postfix evaluation function:
input: 23+3^
Success #stdin #stdout 0s 9424KB
(4) postfix evaluation program:
For evaluation of postfix expression, the algorithm is easy:
(1) parse through the expression character by character.
(2) if a character is operand then push it to stack.
else if it is an operator, pop two operands from the stack and then perform the operation as
new_item=popped_2 operator popped_1
push this new_item back to stack.
(3) at the end of the loop of step 2, pop the stack once as you must only have the result left in the stack. print it. You are done. voila!!
Here is the function named as postfix_evaluation!
(5) postfix evaluation function:
void *postfix_evaluation(char *string,int length)
{ int i; stack operators;
for(i=0;i<length;i++)
{
char c;
c=string[i];
if(c==plus || c==subtract || c==multi || c==divi || c==power)
{
int a =pop();
int b=pop();
if(c==plus)
{
int result=b+a;
push(result);
}
if(c==subtract)
{
int result=b-a;
push(result);
}
if(c==multi)
{
int result=b*a;
push(result);
}
if(c==divi)
{
int result=b/a;
push(result);
}
if(c==power)
{
int result=pow(b,a);
push(result);
}
}
else
{ int k=c-'0';
push(k);
// printf("%d",k);
}
}
int d=pop();
printf("%d",d);
}
(6) Hey, if you are still reading this post, you may need the ready-made function for postfix evaluation. Here it is for you:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define SIZE 100
int count=0;
typedef struct node{
int value;
struct stack *next;
struct stack *prev;
}stack;
stack *bottom=NULL;
stack *top=NULL;
stack *createnode(int a)
{
stack *newstack;
newstack=(stack*)calloc(1,sizeof(stack));
newstack->value=a;
newstack->prev=NULL;
newstack->next=NULL;
return newstack;
}
int isempty()
{
if(count==0)
{return 1;}
else
{return 0;}
}
int isfull()
{
if(count==SIZE)
{return 1;}
else
{return 0;}
}
void push(int a)
{ if(isfull()==1)
{
printf("overflow condition: stack full");
}
else
{count+=1;
stack *newstack = createnode(a);
if(bottom==NULL)
{
bottom=newstack;
top=bottom;
}
else
{
top->next=newstack;
newstack->prev=top;
top=newstack;
}
}
}
char peek()
{
return top->value;
}
char pop()
{ if(isempty()==1)
{
printf("underflow condition:empty stack");
}
else
{if(count==1)
{ int c;
c=top->value;
top=NULL;
bottom=NULL;
count=count-1;
return c;
}
else
{int c;
c=top->value;
top=top->prev;
top->next=NULL;
count=count-1;
return c;
}
}
}
char plus=43;
char multi=42;
char divi=47;
char power=94;
char left=40;
char right=41;
char subtract=45;
void *postfix_evaluation(char *string,int length)
{ int i; stack operators;
for(i=0;i<length;i++)
{
char c;
c=string[i];
if(c==plus || c==subtract || c==multi || c==divi || c==power)
{
int a =pop();
int b=pop();
if(c==plus)
{
int result=b+a;
push(result);
}
if(c==subtract)
{
int result=b-a;
push(result);
}
if(c==multi)
{
int result=b*a;
push(result);
}
if(c==divi)
{
int result=b/a;
push(result);
}
if(c==power)
{
int result=pow(b,a);
push(result);
}
}
else
{ int k=c-'0';
push(k);
}
}
int d=pop();
printf("%d",d);
}
// driver code , the main function
int main(void)
{ char inversion[200];
printf("give the postfix expression\n");
scanf("%s",&inversion);
int longer=strlen(inversion);
postfix_evaluation(inversion,longer);
return 0;
}
Example:input: 23+3^
Success #stdin #stdout 0s 9424KB
give the postfix expression 125
Comments
Post a Comment