C Program to implement Conversion of Infix to Prefix expression

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 5 typedef struct stack { char data[MAX]; int top; }st; void createStack(st *s) { s->top=-1; } void push(st *s,char ele) { s->top++; s->data[s->top]=ele; } char pop(st *s) { return(s->data[s->top--]); } int priority(char symbol) { switch(symbol) { case '+': case '-':return(2); case '*': case '/':return(4); case '^':return(5); case '(': case ')': case '#':return(1); } } int isoperator(char symbol) { switch(symbol) { case '(': case ')': case '+': case '-': case '*': case '/': case '^':return(1); default:return(0); } } void convert(char *infix,st *s) { char *prefix,symbol; int i=0,j=0; prefix=(char *)malloc(sizeof(char)*50); infix=strrev(infix);/*reverse the infix expression*/ s->data[++(s->top)]='#';/*'#' delimeter is used for end of expression*/ while(infix[i]!='\0') { symbol=infix[i]; if(isoperator(symbol)==0) { /*if symbol is operand then add it to prefix expression*/ prefix[j]=symbol; j++; } else if(symbol==')') { /*if it is closing parentheses then push it to stack*/ push(s,symbol); } else if(symbol=='(') { /*if it is opening parentheses then pop operators from stack until corresponding parentheses is encountered*/ while(s->data[s->top]!=')') { prefix[j]=pop(s); j++; } pop(s);/*pop and discard the closing parentheses*/ } else { /*if the incoming priority of operator is greater or equal to stack top operator then push it into stack*/ if(priority(symbol)>=priority(s->data[s->top])) { push(s,symbol); } else { /*if the incoming operator has lowest priority then pop the stack top operator and add to prefix expression*/ while(priority(symbol)<priority(s->data[s->top])) { prefix[j]=pop(s); j++; } push(s,symbol); } } i++; } while(s->data[s->top]!='#') { /*unstack the remaining operators when input is no more*/ prefix[j]=pop(s); j++; } prefix[j]='\0'; prefix=strrev(prefix);/*make the string reverse*/ i=0; while(prefix[i]!='\0') { if(prefix[i]=='#') prefix[i]=prefix[i+1]; i++; } printf("\nprefix is:%s",prefix); } int main() { char *infix; st s; createStack(&s); infix=(char *)malloc(sizeof(char)*50); printf("\nenter infix exp:"); scanf("%s",infix); convert(infix,&s); return 0; }

Happy Exploring!