#include<stdio.h>
#define size 50
char s[size];
int top=-1;
void strrev(char*);
void push(char elem)
{
s[++top]=elem;
}
char pop()
{
return (s[top--]);
}
int precedence(char elem)
{
switch(elem)
{
case'@':return 0;
case')':return 1;
case'+':
case'-':return 2;
case'*':
case'/':return 3;
}
}
void main()
{
char infix[size],prefix[size],ch,elem;
char* x;
int i=0,l=0;
int k=0;
printf("Enter the expression:\t");
scanf("%s",infix);
push('@');
strrev(infix);
while ((ch=infix[l])!='\0')
{
if (ch==')')
{
push(ch);
}
else if (ch=='(')
{
while(s[top]!=')')
prefix[k++]=pop();
elem=pop();
}
else
{
if(precedence(s[top])<=precedence(ch))
{
push(ch);
}
else
{
while(precedence(s[top])>precedence(ch))
prefix[k++]=pop();
push(ch);
}
}
l++;
}
while(s[top]!='@')
prefix[k++]=pop();
prefix[k]='\0';
strrev(prefix);
strrev(infix);
printf("Given infix expression:\t%s\nConverted Prefix expression:\t%s\n",infix,prefix);
}
void strrev(char *w)
{
int i=0;
while(w[i]!='\0')
{
push(w[i]);
i++;
}
int j=0;
while(w[j]!='\0')
{
w[j]=pop();
j++;
}
}