Skip to content

Instantly share code, notes, and snippets.

@anubhavshrimal
Created March 1, 2016 19:59
Show Gist options
  • Save anubhavshrimal/66e6e8b438d7662f6fa5 to your computer and use it in GitHub Desktop.
Save anubhavshrimal/66e6e8b438d7662f6fa5 to your computer and use it in GitHub Desktop.
convert an infix expression to prefix expression
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *link;
}*top;
int check(char c);
void insert(char c);
void push(char c,int value);
void pop();
char printVal(int value);
int j;
char b[7];
int main()
{
int i,value;
char a[7]={'a','*','b','+','c','/','e'};
j=0;
for(i=6;i>=0;i--)
{
value=check(a[i]);
if(value==0)
insert(a[i]);
else
push(a[i],value);
}
while(top!=NULL)
pop();
for(i=6;i>=0;i--)
printf("%c ",b[i]);
return 0;
}
int check(char c)
{
if(c=='+')
return 1;
if(c=='-')
return 2;
if(c=='*')
return 3;
if(c=='/')
return 4;
else
return 0;
}
void insert(char c)
{
b[j]=c;
j++;
}
void push(char c,int value)
{
struct node *temp=((struct node *)malloc(sizeof(struct node)));
temp->num=value;
if(top==NULL)
{
top=temp;
temp->link=NULL;
}
else
{
if(value==4)
{
while(top!=NULL && (top->num==3||top->num==4))
pop();
temp->link=top;
top=temp;
return;
}
if(value==3)
{
while(top!=NULL && (top->num==3||top->num==4))
pop();
temp->link=top;
top=temp;
return;
}
if(value==2)
{
while(top!=NULL && (top->num==2||top->num==1||top->num==3||top->num==4))
pop();
temp->link=top;
top=temp;
return;
}
if(value==1)
{
while(top!=NULL && (top->num==2||top->num==1||top->num==3||top->num==4))
pop();
temp->link=top;
top=temp;
return;
}
}
}
void pop()
{
char ch=printVal(top->num);
insert(ch);
struct node *ptr=top;
top=top->link;
free(ptr);
}
char printVal(int value)
{
if(value==1)
return '+';
if(value==2)
return '-';
if(value==3)
return '*';
if(value==4)
return '/';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment