Program to Convert Infix to Postfix Expression
Infix expressions are human-readable but it is Time consuming for machines to read. That's why we need to convert infix to postfix expression. Before going to convert infix to postfix expression we need to understand infix and postfix expressions.
What is Infix Expression?
Infix expression consists of Operators between operands. An expression is called Infix Expression if the operators are included between the operands and easily calculated by humans.
Example of Infix Expression
- A+B+C+D
- (A*B)+C+D
- 1*(2+9)+8-(2+4^6)
What is Postfix Expression?
Postfix expression is the notation in which operators are placed after the operands. This notation is easily evaluated and understood by computers.
Example of Postfix Expression
- AB+C+D+
- AB*C+D+
- ABC*EF-/+
Infix to postfix precedence rules
Here is the precedence and associativity of operators in the conversion of Infix to postfix expression. Here is the table representing operator precedence and associativity in C.
Precedence & Associativity |
||
|---|---|---|
| Operator type | Operators | Associativity |
| Unary | +,-,*,&,++,!,~ | Right to Left |
| Multiplicative | /,*,% | Left to Right |
| Brackets | (),[],{},-> | Left to Right |
| Relational | <<,>>,<,> | Left to Right |
| Equality | = =,!= | Left to Right |
| Bitwise XOR | & | Left to Right |
| Bitwise AND | ^ | Left to Right |
Rules to Convert Infix to Post Expression
To convert infix to postfix expression using stack use the following rules:
- Read all Characters from left to right in the given Arithmetic expression.
- If you get Operand then print it as it is.
- If the character is operator or parenthesis then push it into the stack.
- If you get an operator then check for the precedence of the operator.
- If reading characters have lower precedence over the characters in Stack, then pop out those characters and then push this into the stack.
Precedence of Operators | |
|---|---|
| Operator type | Precedence |
| Exponentiation | High |
| Divide and Multiplication | Medium |
| Addition & Subtraction | Low |
| NOT | High |
| AND | Medium |
| OR | Low |
Let us see the code for converting infix expression to postfix expression in different programming languages.
Also, Read - [ Largest area of Rectangle in Histogram ]
Conversion of Infix to Postfix expression using Stack
Here is Algorithm to convert infix to postfix expression in Java and C++.
Infix to postfix conversion in C++
#include<bits/stdc++.h>
using namespace std;
//Function to check precedence and associativity
int value(char c)
{
if(c == '^')
return 4;
else if(c == '/')
return 3;
else if(c=='*')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return 0;
}
void infipost(string s)
{
string postfix="";
stack <char> st;
for(int i=0;i<s.length();i++)
{
if(s[i]=='(') st.push(s[i]);
else if((s[i]>='a' && s[i]<='z') ||(s[i]>='A' && s[i]<='Z') || (s[i]>='0' && s[i]<='9'))
{
postfix=postfix+s[i];
}
else if((s[i]=='/' || s[i]=='*' || s[i]=='+'||s[i]=='-' ||s[i]=='^') &&(st.size()==0))
{
st.push(s[i]);
}
else if(s[i]=='/' || s[i]=='*' || s[i]=='+'||s[i]=='-' ||s[i]=='^')
{
while(value(s[i])<=value(st.top()))
{
postfix=postfix+st.top();
st.pop();
}
st.push(s[i]);
}
else if(s[i]==')')
{
while(st.top()!='(')
{
postfix=postfix+st.top();
st.pop();
}
st.pop();
}
}
cout<<"PostFix Expression is : "<<postfix<<endl;
}
int main ()
{
string s="(P/Q+(R-T)*U)";
infipost(s);
return 0;
}
Infix to postfix conversion in Java
import java.util.*;
public class infixToPostfix
{
static Stack operators = new Stack();
public static void main(String argv[])
{
String infix="(P/Q+(R-T)*U)";
System.out.println("Postfix expression is :" + postfix(infix));
}
private static String postfix(String infix)
{
char symbol;
String postfix = "";
for(int i=0;i<infix.length();++i)
{
symbol = infix.charAt(i);
if (Character.isLetter(symbol))
postfix = postfix + symbol;
else if (symbol=='(')
{
operators.push(symbol);
}
else if (symbol==')')
{
while (operators.peek() != '(')
{
postfix = postfix + operators.pop();
}
operators.pop();
}
else
{
while (!operators.isEmpty() && !(operators.peek()=='(') && pre(symbol) <= pre(operators.peek()))
postfix = postfix + operators.pop();
operators.push(symbol);
}
}
while (!operators.isEmpty())
postfix = postfix + operators.pop();
return postfix;
}
static int precedence(char x)
{
if(c == '^')
return 4;
else if(c == '/')
return 3;
else if(c=='*')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return 0;
}
}
OutPut :
Postfix Expression is : P Q / R T - U * +
Solution of Infix to Postfix expression only at courpedia.com
Practice this Problem at Leetcode - Infix to postfix
