Infix to Prefix | Infix to Postfix Conversion in Data Structure

In this article infix to prefix we give the information about infix to postfix conversion in data structure. In Infix expression, the operator is written in between the operand. This is our general mathematics-writing rule.

Infix, Prefix and Postfix Expressions

There are three types of arithmetic expressions according to polish notation

  1. Infix Expression
  2. Prefix Expression
  3. Postfix Expression

Expression contains number of operands combined using operators. According to the position of operator, the above three expressions are decided.

  1. Infix Expression: In Infix expression, the operator is written in between the operand. This is our general mathematics-writing rule.

Example: X + Y

  1. Prefix Notation: In Prefix notation, the operator is written before the operands.

Example: + X Y

  • Postfix Expressions: In Postfix notation, the operator is written after the operand.

Example: X Y +

Notation Conversion

We can convert infix expression in to prefix as well as in postfix expression. If expression contains more than one operator then at the time of conversion we must follow the rule called as BODMOS rule.

Let us take some expressions, convert them in prefix and postfix expression

Conversion from Infix to Prefix

Infix Expression                             Conversion to Prefix Expression

A + B*C                                              A + (B*C)       : Put Parenthesis    

                                                          A + (*BC)       : Converting multiplication.

                                                           +A(*BC)         : Converting Addition

                                                          +A*BC            : Resulted Prefix Expression

Conversion from Infix to Postfix

Infix Expression                             Conversion to Postfix Expression

X + Y*Z                                              X + (Y*Z)        : Put Parenthesis    

                                                          X + (YZ*)        : Converting multiplication.

                                                          X(YZ*)+          : Converting Addition

                                                          XYZ*+            : Resulted Postfix Expression

Example

  1. Convert the following infix expression to postfix

A * B + C / D

First, we will parenthesis the expression according to precedence of operator

(A * B) + (C / D)

(AB*) + (C / D)

(AB*) + (CD/)

AB*CD/+

Postfix expression is: AB*CD/+

Convert the following infix expression to postfix

A + B / C – D

First, we will parenthesis the expression according to precedence of operator

A + (B / C) – D

A + (BC/) – D

(A + BC/) – D

(ABC/+) – D

ABC/+D-

Postfix expression is: ABC/+D-

Algorithm to converting Infix to Postfix

Step 1             Start

Step 2             Stack is the empty stack.

Step 3             Read a character from infix expression from left to right.

Step 4             If input character is operand then, add it into postfix string.

Step 5             If input character is a left parenthesis then, PUSH it to stack.

Step 6             If input character is an operator then,

  1. Repeatedly POP from stack and popped operator to postfix expression if it has the same or higher precedence than input operator.
  2. PUSH input operator.

Step 7 If input character is closing parenthesis then,

  1. Repeatedly POP from stack and add it to postfix string until a left parenthesis is encountered.

Step 8             Repeat from step 3 until the infix expression does not end.

Step 9             POP from stack and add to postfix string until stack is not empty.

Step 10          Stop

Example

Following example shows the status of stack after every step in tabular form. Convert (A+B)*(C/D)

 Character Scanned   Stack  Postfix Expression

 1

( (

2

A (

A

3

+ (+

A

4

B (+ AB
5 )

AB+

6

* * AB+

7

( *(

AB+

8 C *(

AB+C

9

/ *(/ AB+C
10 D *(/

AB+CD

11

) * AB+CD/
12

AB+CD/*

Example: This Program Converts given infix expression into postfix expression

 #include<stdio.h>

#include<conio.h>

#include<string.h>

#define MAX 30

struct stack

{

            char data[MAX];

            int top;

};

struct stack s;

void main()

{

            char infix[MAX];

            void convert(char[]);

            void push(char);

            char pop();

            int preced(char ch);

            clrscr();

            s.top=-1;

            printf(“\n Enter the Infix Expression: ”);

            scanf(“%s”,infix);

            convert(infix);

            getch();

}

void push (char x)

{

            if(s.top==MAX-1)

                        printf(“\n Stack Overflow”);

            else

                        {

                                    s.top+=1;

                                    s.data[s.top]=x;

                        }

}

char pop()

{

            if(s.top==-1)

            {

                        printf(“\n Stack is Empty”);

            }

            else

                        return (s.data[s.top–]);

            }

            int preced(char ch)

            {

                        if (ch==’+’ || ch==’-’)

                                    return 1;

                        else

                                    if(ch==’*’ || ch==’/’ || ch==’%’)

                                    return 2;

                        else

                                    if(ch==’^’)

                                    return 3;

            }

void convert (char infix[])

{

            Int length,pr;

            static int i=0,pos=0;

            char ch, temp;

            char postfix[40];

            while(i<length)

            {

                        ch=infix[i];

                        switch(ch)

                        {

                                    case ‘(’:push(ch);

                                                break;

                                    case ‘)’:temp=pop();

                                                while(temp!=’(‘)

                                                {

                                                            postfix[pos]=temp;

                                                            pos++;

                                                            temp=pop();

                                                }

                                                break;

                                    case ‘+’:

                                    case ‘-’:

                                    case ‘*’:

                                    case ‘/’:

                                    case ‘%’:

                                    case ‘^’:

                                                            pr=preced(ch);

                                                            while(s.top!=1 && pr<=preced(s.data)[s.top]))

                                                                        postfix[pos++]=pop();

                                                            push(ch);

                                                            break;

                                    default:           postfix[pos++]=ch;

                                                            break;

                        }

                        i++;

            }

            while(s.top>=0)

            {

                        temp=pop();

                        postfix[pos++]=temp;

            }

            postfix[pos++]=’\0’;

            printf(“%s”,postfix);

}

Algorithm to evaluate a Postfix expression

Step 1             Start

Step 2             Stack is the empty stack.

Step 3             Read a character from postfix string

Step 4             If input character is operand then, PUSH it into stack.

Step 5             If input character is a operator then,

  1. POP two operands from the stack
  2. Apply the operator to these two operands
  3. PUSH the result into stack

Step 6             If postfix expression has not ended go to step 3

Step 7 POP from stack and display

Step 8 Stop

Example

Following example shows the status of stack after every step in tabular form.

Evaluate AB+CDD-/                        Let A=7, B=2, C=15, D=12

 Character Scanned Stack  Operand-1  Operand-2

 Result

 1

7

7

 2 2

7,2

3

+ 9 7 2

9

4 15

9,15

5

12

9,15,12

6 9,3 15 12

3

7

/ 3 9 3

3

Example: This Programme valuates valid given postfix expression

#include<stdio.h>

#include<conio.h>

#include<math.h>

struct stack

{

            float data[10];

            int top;

};

struct stack s;

void main()

{

            int i=0;

            char expr[20];

            float value[20],result;

            void push(char);

            float pop();

            float eval(char[],float[]);

            clrscr();

            s.top=-1;

            printf(“\n Enter a valid Postfix Expression:”);

            scanf(“%s”,expr);

            while(expr[i]!=’\0’)

            {

                        if(isalpha(expr[i]))

                        {

                                    fflush(stdin);

                                    printf(“\n Enter the value of %c: ”,expr[i]);

                                    scanf(“%f”,&value[i]);

                        }

                        i++;

            }

            result=eval(expr,value);

            printf(“\n The result is: %f”,result);

            getch();

}

void push(char num)

{

            s.data[++s.top]=num;

}

float pop()

{

            return(s.data[s.top–]);

}

float eval(char expr[],float data[])

{

            int i=0;

            float op1,op2,result;

            char ch;

            while(expr[i]!=’\0’)

            {

                        ch=expr[i];

                        if(isalpha(expr[i]))

                                    push(data[i]);

                        else

                                    {

                                                op2=pop();

                                                op1=pop();

                                                switch(ch)

                                                {

                                                            case ‘+’: push(op1+op2);

                                                                                    break;

                                                            case ‘-’: push(op1-op2);

                                                                                    break;

                                                            case  ‘/’ : push(op1/op2);

                                                                                    break;

                                                            case ‘*’: push(op1*op2);

                                                                                    break;

                                                            case’^’: push(pow(op1,op2));

                                                                                    break;

                                                }

                                    }

                                    i++;

            }

            result=pop();

            return(result);

}

Algorithm to convert Infix Expression to Prefix Expression

Example:

Infix Expression:                  (A+B)*C

Prefix Expression:               *+ABC

Step 1             Start

Step 2             Read a character from postfix string.

Step 3              If a character is opening parenthesis or operator then,

  1. PUSH it into Operator_Stack.

Step 4             If a character is an operand then,

  1. PUSH it into Operator_Stack.

Step 5             If a character is a closing parenthesis then,

                        Repeat following steps until popped character is not equal to opening parenthesis,

  1. POP two operands as Operand-1 and Operand-2 from Operand_Stack
  2. Form an expression as– Character Operand-1, Operand-2
  3. PUSH expression in Operand_Stack.

Step 6             Repeat from step 2 until infix expression does not end.

Step 7 POP from Operand_Stack and display.

Step 8             Stop

Example:

Following example shows the status of stack after every step in tabular form.

Evaluate (A+B)*C     *+ABC

 Character Scanned  Operand_Stack  Operator_Stack  Prefix Expression

 1

(

(

 2

A A

(

 3

+ A

(+

 4

B A,B
 5 ) +AB

+AB

 6

* +AB *
 7 C +AB,C *

 8

) *+ ABC

*+ ABC

Related Link:

Some More: DBMS/ WT/ DMDW

Santosh Nalawade

Work as Assistant Professor and Web Developer.

Leave a Reply

Your email address will not be published. Required fields are marked *