Infix expression to postfix expression conversion

/* program on conversion of infix to postfix expression */

#include"stdio.h"
#include"stdlib.h"

#define OPT 0
#define OPND 1
#define LP 2
#define RP 3

char infix[100], postfix[100]; /* global variables declare here */

struct stack
{
char info;
struct stack *next;
} *stk;


/* main function here */

int main(void)
{
clrscr();
printf("\nEnter a infix expression : ");
fflush(stdin);
gets(infix);
intopost();
printf("\nPostfix expression is : %s", postfix);
getch();
return 0;
}


/* push function here */

push(struct stack *s, char n)
{
struct stack *temp;
temp = (struct stack *)malloc(sizeof(struct stack));
temp->info = n;
temp->next = s;
stk = temp;
}

/* Pop function here */

char pop(struct stack *s)
{
char ch;
if(s!=NULL)
{
ch = s->info;
stk = s->next;
free(s);
}
return ch;
}
/* get character type form infix expression */
int gettype(char ch)
{
if(ch=='+'|| ch == '-' || ch == '*' || ch == '/' || ch == '%')
return OPT;
else if(ch == '(')
return LP;
else if(ch == ')')
return RP;
else
return OPND;
}

/* get precedence of operator */
prec(char op)
{
switch(op)
{
case ')':
case '(': return 0;
case '+':
case '-': return 1;
case '*':
case '/':
case '%': return 2;
case '^': return 3;
}
}

/* convert infix to postfix expression */
intopost()
{
int i,p, type, pr;
char ch, op;

for(i=0, p=0; infix[i]!='\0';i++)
{
ch = infix[i];
type = gettype(ch);
switch(type)
{
case OPND: postfix[p++] = ch;
break;
case LP: push(stk, ch); break;
case OPT: pr = prec(ch);
while(stk!=NULL&& pr<=prec(stk->info))
postfix[p++] = pop(stk);
push(stk, ch);
break;
case RP: while(stk!=NULL && (op = pop(stk))!='(')
postfix[p++] = op;
break;
}
}

while(stk!=NULL)
postfix[p++] = pop(stk);
postfix[p] = '\0';
}

Posted in: Stacks