# Infix to Postfix Converter | Infix to Prefix Conversion

In this article infix to postfix converter we give the information about 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

#### Infix to Postfix Converter:

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            : 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.

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:

#### Infix to Postfix Converter:

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

#### Some More:

POP- Introduction to Programming Using ‘C’

DS – Data structure Using C

OOP – Object Oriented Programming

Java Programming

DBMS – Database Management System

RDBMS – Relational Database Management System