Infix to Prefix Conversion Using Stack

Infix to Prefix Conversion

Algorithm of Infix to Prefix

Step 1. Push “)” onto STACK, and add “(“ to end of the A

Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty

Step 3. If an operand is encountered add it to B

Step 4. If a right parenthesis is encountered push it onto STACK

Step 5. If an operator is encountered then:

a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same 

        or higher precedence than the operator.

     b. Add operator to STACK

Step 6. If left parenthesis is encontered then

a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd)

b. Remove the left parenthesis

Step 7. Exit

Infix to prefix conversion

Expression = (A+B^C)*D+E^5

Step 1. Reverse the infix expression.

               5^E+D*)C^B+A(

Step 2. Make Every '(' as ')' and every ')' as '(' 

                5^E+D*(C^B+A)

Step 3. Convert expression to postfix form.

A+(B*C-(D/E-F)*G)*H

Expression	Stack	Output	Comment
5^E+D*(C^B+A)	Empty	-	Initial
^E+D*(C^B+A)	Empty	5	Print
E+D*(C^B+A)	^	5	Push
+D*(C^B+A)	^	5E	Push
D*(C^B+A)	+	5E^	Pop And Push
*(C^B+A)	+	5E^D	Print
(C^B+A)	+*	5E^D	Push
C^B+A)	+*(	5E^D	Push
^B+A)	+*(	5E^DC	Print
B+A)	+*(^	5E^DC	Push
+A)	+*(^	5E^DCB	Print
A)	+*(+	5E^DCB^	Pop And Push
)	+*(+	5E^DCB^A	Print
End	+*	5E^DCB^A+	Pop Until '('
End	Empty	5E^DCB^A+*+	Pop Every element

Step 4. Reverse the expression.

                +*+A^BCD^E5 

Result

+*+A^BCD^E5 

Write a Program to Implements Infix to prefix in C Using Array

# include <stdio.h>
#include <conio.h>
# include <string.h>
# define MAX 20;

void infixtoprefix(char infix[20],char prefix[20]);
void reverse(char array[30]);
char pop();
void push(char symbol);
int isOperator(char symbol);
int prcd(symbol);
int top=-1;
char stack[MAX];

void main() {
char infix[20],prefix[20],temp;
printf("Enter infix operation: ");
gets(infix);
infixtoprefix(infix,prefix);
reverse(prefix);
puts((prefix));
getch();
}
//--------------------------------------------------------
void infixtoprefix(char infix[20],char prefix[20]) {
int i,j=0;
char symbol;
stack[++top]='#';
reverse(infix);
for (i=0;i<strlen(infix);i++) {
symbol=infix[i];
if (isOperator(symbol)==0) {
prefix[j]=symbol;
j++;
} else {
if (symbol==')') {
push(symbol);
} else if(symbol == '(') {
while (stack[top]!=')') {
prefix[j]=pop();
j++;
}
pop();
} else {
if (prcd(stack[top])<=prcd(symbol)) {
push(symbol);
} else {
while(prcd(stack[top])>=prcd(symbol)) {
prefix[j]=pop();
j++;
}
push(symbol);
}
//end for else
}
}
//end for else
}
//end for for
while (stack[top]!='#') {
prefix[j]=pop();
j++;
}
prefix[j]='\0';
}
////--------------------------------------------------------
void reverse(char array[30]) // for reverse of the given expression {
int i,j;
char temp[100];
for (i=strlen(array)-1,j=0;i+1!=0;--i,++j) {
temp[j]=array[i];
}
temp[j]='\0';
strcpy(array,temp);
return array;
}
//--------------------------------
char pop() {
char a;
a=stack[top];
top--;
return a;
}
//----------------------------------
void push(char symbol) {
top++;
stack[top]=symbol;
}
//------------------------------------------
int prcd(symbol) // returns the value that helps in the precedence {
switch(symbol) {
case '+':
        case '-':
        return 2;
break;
case '*':
        case '/':
        return 4;
break;
case '$':
        case '^':
        return 6;
break;
case '#':
        case '(':
        case ')':
        return 1;
break;
}
}
//-------------------------------------------------
int isOperator(char symbol) {
switch(symbol) {
case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '$':
        case '&':
        case '(':
        case ')':
        return 1;
break;
default:
        return 0;
// returns 0 if the symbol is other than given above
}

}

Write a Program implement Infix to prefix Using Pointer in C.

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define MAX 50
struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top, l ;
} ;

void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
void show ( struct infix ) ;

void main( )
{
struct infix q ;
char expr[MAX] ;
clrscr( ) ;
initinfix ( &q ) ;
printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;
setexpr ( &q, expr ) ;
convert ( &q ) ;
printf ( "The Prefix expression is: " ) ;
show ( q ) ;
getch( ) ;
}
/* initializes elements of structure variable */
void initinfix ( struct infix *pq )
{
pq -> top = -1 ;
strcpy ( pq -> target, "" ) ;
strcpy ( pq -> stack, "" ) ;
pq -> l = 0 ;
}
/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
pq -> s = str ;
strrev ( pq -> s ) ;
pq -> l = strlen ( pq -> s ) ;
*( pq -> target + pq -> l ) = '\0' ;
pq -> t = pq -> target + ( pq -> l - 1 ) ;
}
/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
if ( pq -> top == MAX - 1 )
printf ( "\nStack is full.\n" ) ;
else
{
pq -> top++ ;
pq -> stack[pq -> top] = c ;
}
}
/* pops an operator from the stack */
char pop ( struct infix *pq )
{
if ( pq -> top == -1 )
{
printf ( "Stack is empty\n" ) ;
return -1 ;
}
else
{
char item = pq -> stack[pq -> top] ;
pq -> top-- ;
return item ;
}
}
/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
char opr ;
while ( *( pq -> s ) )
{
if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
{
pq -> s++ ;
continue ;
}
if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
*( pq -> t ) = *( pq -> s ) ;
pq -> s++ ;
pq -> t-- ;
}
}
if ( *( pq -> s ) == ')' )
{
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}
if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' || *( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
{
if ( pq -> top != -1 )
{
opr = pop ( pq ) ;
while ( priority ( opr ) > priority ( *( pq -> s ) ) )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
push ( pq, opr ) ;
push ( pq, *( pq -> s ) ) ;
}
else
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}
if ( *( pq -> s ) == '(' )
{
opr = pop ( pq ) ;
while ( opr != ')' )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
pq -> s++ ;
}
}
while ( pq -> top != -1 )
{
opr = pop ( pq ) ;
*( pq -> t ) = opr ;
pq -> t-- ;
}
pq -> t++ ;
}
/* returns the priotity of the operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
/* displays the prefix form of given expr. */
void show ( struct infix pq )
{
while ( *( pq.t ) )
{
printf ( " %c", *( pq.t ) ) ;
pq.t++ ;
}
}


Output:

Enter an Expression in Infix form: (A+B*C)

The Prefix expression is: +A*BC