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


  • Prefix Infix Postfix converter Tool Online






  • 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
    ExpressionStackOutputComment
    5^E+D*(C^B+A)Empty-Initial
    ^E+D*(C^B+A)Empty5Print
    E+D*(C^B+A)^5Push
    +D*(C^B+A)^5EPush
    D*(C^B+A)+5E^Pop And Push
    *(C^B+A)+5E^DPrint
    (C^B+A)+*5E^DPush
    C^B+A)+*(5E^DPush
    ^B+A)+*(5E^DCPrint
    B+A)+*(^5E^DCPush
    +A)+*(^5E^DCBPrint
    A)+*(+5E^DCB^Pop And Push
    )+*(+5E^DCB^APrint
    End+*5E^DCB^A+Pop Until '('
    EndEmpty5E^DCB^A+*+Pop Every element


    Step 4. Reverse the expression.
                    +*+A^BCD^E5

    Result

    +*+A^BCD^E5


    Infix to prefix implementation in c : without Pointer

    # include <stdio.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];
    main() {
    	char infix[20],prefix[20],temp;
    	printf("Enter infix operation: ");
    	gets(infix);
    	infixtoprefix(infix,prefix);
    	reverse(prefix);
    	puts((prefix));
    }
    //--------------------------------------------------------
    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
    	}
    }
    


    Infix to prefix implementation in c : with Pointer

    #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++ ;
    	}
    }
    




    Quantitative Aptitude
    Reasoning
    Programming
    Interview