#include<stdio.h>
#include<string.h>
#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40
#define RPP 0
#define AP 1
#define SP 1
#define MP 2
#define DP 2
#define REMP 2
#define NONE 9
void InfixToPrefix();
int getType(char);
int getPrecedence(char);
void push(char);
char pop();
char infix[50],stack[40],prefix[50];
int top;
int main()
{
char ch;
do
{
top=-1;
printf("Enter an Infix expression : ");
gets(infix);
strrev(infix);
InfixToPrefix();
strrev(prefix);
printf("Prefix expression : %s\n",prefix);
printf("Do you want to convert one more (y\\n) : ");
ch=getche();
}while(ch=='y');
return 0;
}
void InfixToPrefix()
{
int i,p,l,type,prec;
char next;
i=p=0;
l=strlen(infix);
while(i<l)
{
type=getType(infix[i]);
switch(type)
{
case RP: push(infix[i]);
break;
case LP: while((next=pop())!=')')
{
prefix[p]=next;
++p;
}
break;
case OPERAND: prefix[p]=infix[i];
++p;
break;
case OPERATOR: prec=getPrecedence(infix[i]);
while((top>-1)&&(prec<getPrecedence(stack[top])))
{
prefix[p]=pop();
++p;
}
push(infix[i]);
break;
}
++i;
}
while(top>-1)
{
prefix[p]=pop();
++p;
}
}
int getType(char sym)
{
switch(sym)
{
case '(': return LP;
case ')': return RP;
case '+':
case '-':
case '*':
case '/':
case '%': return OPERATOR;
default: return OPERAND;
}
}
int getPrecedence(char sym)
{
switch(sym)
{
case ')': return RPP;
case '+': return AP;
case '-': return SP;
case '*': return MP;
case '/': return DP;
case '%': return REMP;
default: return NONE;
}
}
void push(char sym)
{
++top;
stack[top]=sym;
}
char pop()
{
char sym;
sym=stack[top];
--top;
return sym;
}
No Comments