Pointers And Strings

Prefix/Postfix/Infix Notation

Infix To Prefix Conversion

We know that it is convenient to work with expressions which are converted from the infix form to the postfix form.Below I am presenting a program which converts an infix expression into an equivalent prefix expression. Just to remind you, in the prefix form the operator appears before its operands.

#define MAX 100

main( )

{

char target[MAX], *t, str[MAX], *s;

char n1;

int p1, p2, i, top = -1, l ;

static char stack[MAX];

clrscr( ) ;

printf("\nEnter the infix expression;");

gets(str);

s = str;

strrev(str);

l = strlen (str);

t = target + ( l -1 );

while(*s)

{

/*skip whitespace if any*/

if(*s ==' '|| *s == `\t')

{

s++;

continue;

}

/*put digit in target string*/

if(isdigit(*s) || isalpha (*s) )

{

while(isdigit(*s) || isalpha (*s))

{

*t = *s;

t--;

s++;

}

}

if (*s == `)')

{

push(stack, &top, *s);

s++;

}

if(*s == `(')

{

n1 = pop (stack, &top);

while(n1!=`)')

{

*t = n1; t--;

n1 = pop (stack, &top);

}

s++;

}

if(*s == `+'|| *s == `_' || *s == `/' || *s == `%')

{

if(top == -1)

push(stack, &top, *s);

else

{

n1 = pop (stack, &top);

while(priority(n1)>=priority(*s) )

{

*t=n1;

t--;

n1=pop(stack, &top);

push(stack, &top, n1);

push(stack, &top, *s);

}

s++;

}

}

while(top!= -1)

{

n1 = pop(stack, &top);

*t = n1; t--;

}

*(target + |) = `\0';

t++;

while (*t)

{

printf("%c", *t);

t++;

}

getch();

}

priority(char ele)

{

int pri;

char a, b, c;

if(ele == `+' || ele == `/' || ele == `%')

pri = 2;

else

{

if(ele == `+' || ele == `_')

pri = 1;

else

pri = 0;

}

return pri;

}

push(char*stk, int*sp, char item)

{

if(*sp == MAX)

printf("\nStack is full");

else

{

*sp = *sp + 1; stk[*sp] = item;

}

}

pop (char *stk, int*sp)

{

int item;

if(*sp == -1)

{

printf("\nStack is empty");

return(-1);

}

else

{

item = stk[*sp];

*sp = *sp - 1;

return(item);

}

}

}