Postfix to Infix Conversion
“Postfix to Infix conversion” is a classic example of stack data structure. Stack can be used to convert given postfix expression to corresponding infix expression.
Operator: Operator are symbols that instruct the computer to perform simple and single tasks. Examples of operators includes + (Addition), – (Subtraction), * (multiplication),… and many more.
Operand: Operands are values or variable on which operator works its tasks. Examples of Operand includes “a”, “b”, 23, 12,.. and many more.
The steps required for Postfix to Infix Conversion are as follows:
- Scan the postfix expression from left to right.
- Initialize an empty string stack.
- If the scanned character is operand, push it into stack.
- Else if the scanned character is operator, pop two strings from stack, namely, temp1 and temp2, and push: (temp2 operator temp1) into stack.
- Repeat steps from 3 to 4 until all the characters from the string are scanned.
- In the end, only one valid infix string will be present in the stack, pop it and return it.
Example
Suppose, we want to convert the following postfix expression to infix expression
Algorithm for Postfix to Infix Conversion
Algo postfix_2_infix (postfix)
{ // input- valid postfix expression
//output- equivalent infix expression
1. Createstack (stack).
2. i=0
3. loop(i<sizeof(stack))
{
a.if postfix[i] is an operator
{
operand2=popstack().
operand1=popstack().
temp= concatenate “(“+ operand1 + postfix[i] + operand2 + “)”.
pushstack (temp).
}
b.else if postfix[i] is an operand
Then push postfix[i] into stack.
c.Increment i with 1.
}
4. infix= popstack().
5. Return infix.
}// END OF ALGO.
C++ Program for Postfix to Infix Conversion is as follows:
/* Program for Postfix to Infix Conversion */
#include <iostream>
#include<string>
#define sizes 100
using namespace std;
class stack
{
string item[100];
int top;
public:
stack()
{
top=-1;
}
void push(string str)
{
if(top==sizes-1)
{
cout<<"stack overflow!!\n";
return;
}
top++;
item[top]=str;
}
string pop()
{
int i;
string temp;
if(top==-1)
{
cout<<"stack underflow!!\n";
return "abc";
}
temp = item[top];
top--;
return temp;
}
};
int main(int argc, char** argv)
{
int i,j=0;
stack st;
string postfix,infix;
cout<<"Enter postfix expression:\n";
cin>>postfix;
for(i=0;i<postfix.size();i++)
{
if(postfix[i]=='+' || postfix[i]=='-' || postfix[i]=='*' || postfix[i]=='/' || postfix[i]=='^')
{
string temp,op1,op2;
op2=st.pop();
op1=st.pop();
temp='('+op1+postfix[i]+op2+')';
st.push(temp);
}
else
{
string flag;
flag=flag+postfix[i];
st.push(flag);
}
}
cout<<"The equivalent infix expression is:\n"<<st.pop();
return 0;
}
OUTPUT: Enter postfix expression: abc*de-/+ The equivalent infix expression: ((a+((b*c)/(d-e))))
Related Posts:
- Postfix to Prefix Conversion
- Infix to Postfix Conversion
- Infix to Prefix Conversion
- Prefix to Infix Conversion
- Prefix to Postfix Conversion
- Check whether given Parentheses String are Balanced Parentheses or Not.
- Next Greater Element
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Merge Overlapping Intervals using Stacks
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Length of Longest Valid Substring
- Reverse a String using Stack
- Implement two stacks in a single array
- Print Bracket Number
- Next Greater Frequency Element
- Sort a Stack using Temporary Stack