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 to Postfix Converter:
Infix Prefix and Postfix Expressions
There are three types of arithmetic expressions according to polish notation
- Infix Expression
- Prefix Expression
- Postfix Expression
Expression contains number of operands combined using operators. According to the position of operator, the above three expressions are decided.
- Infix Expression: In Infix expression, the operator is written in between the operand. This is our general mathematics-writing rule.
Example: X + Y
- 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) : 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
- 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,
- Repeatedly POP from stack and popped operator to postfix expression if it has the same or higher precedence than input operator.
- PUSH input operator.
Step 7 If input character is closing parenthesis then,
- 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,
- POP two operands from the stack
- Apply the operator to these two operands
- 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,
- PUSH it into Operator_Stack.
Step 4 If a character is an operand then,
- 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,
- POP two operands as Operand-1 and Operand-2 from Operand_Stack
- Form an expression as– Character Operand-1, Operand-2
- 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’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining