Postfix to Infix

Try it on GfG Practice

Postfix to infix conversion involves transforming expressions where operators follow their operands (postfix notation) into standard mathematical expressions with operators placed between operands (infix notation). This conversion improves readability and understanding.

• Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands. 
• Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands. 

Examples: 

Input: abc++
Output: (a + (b + c))
Explanation: Infix expression is (a + (b + c)) for expression abc++

Input: ab*c+
Output: ((a*b)+c)
Explanation: Infix expression is ((a*b)+c) for expression ab*c+

Input: abc+*d/
Output: (((a * (b + c))) / d)
Explanation: Infix expression is (((a * (b + c)))/d) for expression abc+*d/

Approach: Using Stack – O(n) Time and O(n) Space

• Initialize Stack – Create an empty stack.
• Process Input Symbols – Read symbols one by one from the input
• Handle Operands – Push operands onto the stack.
• Handle Operators – Pop the top two values, form an infix expression, and push it back.
• Retrieve Final Expression – The remaining value in the stack is the desired infix expression.

#include <bits/stdc++.h>
using namespace std;

bool isOperand(char x)
{
   return (x >= 'a' && x <= 'z') ||
          (x >= 'A' && x <= 'Z');
}

// Get Infix for a given postfix
// expression
string getInfix(string exp)
{
    stack<string> s;

    for (int i=0; exp[i]!='\0'; i++)
    {
        // Push operands
        if (isOperand(exp[i]))
        {
           string op(1, exp[i]);
           s.push(op);
        }

        // We assume that input is
        // a valid postfix and expect
        // an operator.
        else
        {
            string op1 = s.top();
            s.pop();
            string op2 = s.top();
            s.pop();
            s.push("(" + op2 + exp[i] +
                   op1 + ")");
        }
    }

    // There must be a single element
    // in stack now which is the required
    // infix.
    return s.top();
}

// Driver code
int main()
{
    string exp = "ab*c+";
    cout << getInfix(exp);
    return 0;
}

import java.util.*;

class GFG
{
    
static boolean isOperand(char x)
{
    return (x >= 'a' && x <= 'z') ||
            (x >= 'A' && x <= 'Z');
}

// Get Infix for a given postfix
// expression
static String getInfix(String exp)
{
    Stack<String> s = new Stack<String>();

    for (int i = 0; i < exp.length(); i++)
    {
        // Push operands
        if (isOperand(exp.charAt(i)))
        {
        s.push(exp.charAt(i) + "");
        }

        // We assume that input is
        // a valid postfix and expect
        // an operator.
        else
        {
            String op1 = s.peek();
            s.pop();
            String op2 = s.peek();
            s.pop();
            s.push("(" + op2 + exp.charAt(i) +
                    op1 + ")");
        }
    }

    // There must be a single element
    // in stack now which is the required
    // infix.
    return s.peek();
}

// Driver code
public static void main(String args[])
{
    String exp = "ab*c+";
    System.out.println( getInfix(exp));
}
}

// This code is contributed by Arnab Kundu

def isOperand(x):
    return ((x >= 'a' and x <= 'z') or 
            (x >= 'A' and x <= 'Z')) 

# Get Infix for a given postfix 
# expression 
def getInfix(exp) :

    s = [] 

    for i in exp:     
        
        # Push operands 
        if (isOperand(i)) :         
            s.insert(0, i) 
            
        # We assume that input is a 
        # valid postfix and expect 
        # an operator. 
        else:
        
            op1 = s[0] 
            s.pop(0) 
            op2 = s[0] 
            s.pop(0) 
            s.insert(0, "(" + op2 + i +
                             op1 + ")") 
            
    # There must be a single element in 
    # stack now which is the required 
    # infix. 
    return s[0]

# Driver Code 
if __name__ == '__main__': 

    exp = "ab*c+"
    print(getInfix(exp.strip()))

# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

using System;
using System.Collections;

class GFG
{
    
static Boolean isOperand(char x)
{
    return (x >= 'a' && x <= 'z') ||
            (x >= 'A' && x <= 'Z');
}

// Get Infix for a given postfix
// expression
static String getInfix(String exp)
{
    Stack s = new Stack();

    for (int i = 0; i < exp.Length; i++)
    {
        // Push operands
        if (isOperand(exp[i]))
        {
            s.Push(exp[i] + "");
        }

        // We assume that input is
        // a valid postfix and expect
        // an operator.
        else
        {
            String op1 = (String) s.Peek();
            s.Pop();
            String op2 = (String) s.Peek();
            s.Pop();
            s.Push("(" + op2 + exp[i] +
                    op1 + ")");
        }
    }

    // There must be a single element
    // in stack now which is the required
    // infix.
    return (String)s.Peek();
}

// Driver code
public static void Main(String []args)
{
    String exp = "ab*c+";
    Console.WriteLine( getInfix(exp));
}
}

// This code is contributed by Arnab Kundu

function isOperand(x)
{
    return (x >= 'a' && x <= 'z') ||
            (x >= 'A' && x <= 'Z');
}

// Get Infix for a given postfix
// expression
function getInfix(exp)
{
    let s = [];
  
    for (let i = 0; i < exp.length; i++)
    {
        // Push operands
        if (isOperand(exp[i]))
        {
        s.push(exp[i] + "");
        }
  
        // We assume that input is
        // a valid postfix and expect
        // an operator.
        else
        {
            let op1 = s[s.length-1];
            s.pop();
            let op2 = s[s.length-1];
            s.pop();
            s.push("(" + op2 + exp[i] +
                    op1 + ")");
        }
    }
  
    // There must be a single element
    // in stack now which is the required
    // infix.
    return s[s.length-1];
}

// Driver code
let exp = "ab*c+";
console.log( getInfix(exp));

((a*b)+c)

Related Post

• Infix, Postfix and Prefix Expressions/Notations
• Convert Infix expression to Postfix expression
• Infix to Postfix Conversion using Stack in C++