Postfix to Infix Conversion: Code with Visualization

Written by

Sasank Nasika

Edited by

Kaustubh Saini

Last updated on

May 17, 2025

Converting between different mathematical expression formats is a fundamental skill in computer science and programming. One common conversion task is transforming a postfix expression (also known as Reverse Polish Notation) into an infix expression (the standard notation we use in everyday math). This problem frequently appears in coding interviews and serves as an excellent way to practice stack data structures.

Postfix to Infix Conversion: Code with Visualization

Problem Statement

Given a string containing a valid postfix expression with operands and operators (+, -, *, /, ^), convert it to its equivalent infix expression.

For example:

Input: "ab+"
Output: "(a+b)"

The input string consists of single-character operands (lowercase letters) and the standard arithmetic operators.

Brute Force Approach

Explanation

The straightforward approach to convert a postfix expression to infix involves reading the expression from left to right. However, since postfix expressions don't have explicit parentheses, we need to add them during conversion to maintain the correct operator precedence.

Here's how the brute force algorithm works:

Create an empty stack
Scan the postfix expression from left to right
If the current character is an operand (a letter in our case), push it onto the stack
If the current character is an operator:

Pop the top two elements from the stack
Create a new string by placing the operator between these elements, surrounded by parentheses
Push this new string back onto the stack

After processing all characters, the stack will contain only one element - the infix expression

This approach has a time complexity of O(n) where n is the length of the postfix expression, as we scan each character exactly once. The space complexity is also O(n) for storing the intermediate results in the stack.

Code(Python)

def postfix_to_infix(postfix):
    stack = []
    
    # Scan the postfix expression character by character
    for char in postfix:
        # If the character is an operand (a letter in this case)
        if char.isalnum():
            stack.append(char)
        # If the character is an operator
        else:
            # Pop two operands from stack
            operand2 = stack.pop()
            operand1 = stack.pop()
            
            # Create the infix expression with parentheses and push to stack
            infix = f"({operand1}{char}{operand2})"
            stack.append(infix)
    
    # The final element in the stack is our answer
    return stack[0]

# Example usage
postfix_expr = "ab+"
print(postfix_to_infix(postfix_expr))  # Output: "(a+b)"

Code(C++)

#include <iostream>
#include <stack>
#include <string>

std::string postfixToInfix(const std::string& postfix) {
    std::stack<std::string> stack;
    
    // Scan the postfix expression character by character
    for (char ch : postfix) {
        // If the character is an operand (a letter in this case)
        if (isalnum(ch)) {
            // Convert char to string and push to stack
            stack.push(std::string(1, ch));
        }
        // If the character is an operator
        else {
            // Pop two operands from stack
            std::string operand2 = stack.top(); stack.pop();
            std::string operand1 = stack.top(); stack.pop();
            
            // Create the infix expression with parentheses and push to stack
            std::string infix = "(" + operand1 + ch + operand2 + ")";
            stack.push(infix);
        }
    }
    
    // The final element in the stack is our answer
    return stack.top();
}

int main() {
    std::string postfix_expr = "ab+";
    std::cout << postfixToInfix(postfix_expr) << std::endl;  // Output: "(a+b)"
    return 0;
}

Code(Java)

import java.util.Stack;

public class PostfixToInfix {
    public static String postfixToInfix(String postfix) {
        Stack<String> stack = new Stack<>();
        
        // Scan the postfix expression character by character
        for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            
            // If the character is an operand (a letter in this case)
            if (Character.isLetterOrDigit(ch)) {
                stack.push(Character.toString(ch));
            }
            // If the character is an operator
            else {
                // Pop two operands from stack
                String operand2 = stack.pop();
                String operand1 = stack.pop();
                
                // Create the infix expression with parentheses and push to stack
                String infix = "(" + operand1 + ch + operand2 + ")";
                stack.push(infix);
            }
        }
        
        // The final element in the stack is our answer
        return stack.peek();
    }
    
    public static void main(String[] args) {
        String postfix_expr = "ab+";
        System.out.println(postfixToInfix(postfix_expr));   // Output: "(a+b)"
    }
}

Optimized Approach

Explanation

The brute force approach is actually quite efficient for this problem. However, we can make a small optimization by handling unnecessary parentheses.

In the optimized approach, we'll add parentheses only when necessary based on operator precedence. For example, in the expression "a+bc", the multiplication has higher precedence than addition, so we need parentheses around "bc", but not around the entire expression.

Here's the optimized algorithm:

Create an empty stack
Scan the postfix expression from left to right
If the current character is an operand, push it onto the stack
If the current character is an operator:

Pop the top two elements from the stack
Create a new string by placing the operator between these elements
Add parentheses only when necessary based on operator precedence
Push this new string back onto the stack

After processing all characters, the stack will contain only one element - the infix expression

The time and space complexity remain O(n), but the resulting expression will be more readable with fewer unnecessary parentheses.

Consider the string s = “ab+”

Read 'a'. Since it's an operand, push it onto the stack.

Read 'b'. Since it's an operand, push it onto the stack.

Read '+'. It's an operator, so pop the top two elements from the stack ('b' and 'a'), create the infix expression '(a+b)', and push it back onto the stack.

The string traversal is done the string in our stack is our ans.

<visualization-box>

Code(Python)

def postfix_to_infix_optimized(postfix):
    stack = []
    
    # Define operator precedence (higher value means higher precedence)
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    
    for char in postfix:
        # If the character is an operand
        if char.isalnum():
            stack.append(char)
        # If the character is an operator
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            
            # Check if operand1 is a subexpression and if its outermost operator has lower precedence
            if (len(operand1) > 1 and operand1[0] == '(' and operand1[-1] == ')'):
                # Already has parentheses, keep as is
                pass
            elif (len(operand1) > 1 and 
                  operand1[1] in precedence and 
                  precedence[operand1[1]] < precedence[char]):
                operand1 = f"({operand1})"
            
            # Check if operand2 is a subexpression and if its outermost operator has lower precedence
            if (len(operand2) > 1 and operand2[0] == '(' and operand2[-1] == ')'):
                # Already has parentheses, keep as is
                pass
            elif (len(operand2) > 1 and 
                  operand2[1] in precedence and 
                  precedence[operand2[1]] <= precedence[char]):
                operand2 = f"({operand2})"
            
            # Create the infix expression and push to stack
            infix = f"{operand1}{char}{operand2}"
            stack.append(infix)
    
    return stack[0]

# Example usage
postfix_expr = "ab+c*"
print(postfix_to_infix_optimized(postfix_expr))  # Output: "(a+b)*c"

Code(C++)

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

std::string postfixToInfixOptimized(const std::string& postfix) {
    std::stack<std::string> stack;
    
    // Define operator precedence (higher value means higher precedence)
    std::unordered_map<char, int> precedence;
    precedence['+'] = 1;
    precedence['-'] = 1;
    precedence['*'] = 2;
    precedence['/'] = 2;
    precedence['^'] = 3;
    
    for (char ch : postfix) {
        // If the character is an operand
        if (isalnum(ch)) {
            stack.push(std::string(1, ch));
        }
        // If the character is an operator
        else {
            std::string operand2 = stack.top(); stack.pop();
            std::string operand1 = stack.top(); stack.pop();
            
            // Check if operands need parentheses
            bool needParens1 = false;
            bool needParens2 = false;
            
            if (operand1.length() > 1 && 
                precedence.find(operand1[1]) != precedence.end() && 
                precedence[operand1[1]] < precedence[ch]) {
                needParens1 = true;
            }
            
            if (operand2.length() > 1 && 
                precedence.find(operand2[1]) != precedence.end() && 
                precedence[operand2[1]] <= precedence[ch]) {
                needParens2 = true;
            }
            
            // Create the infix expression
            std::string infix = "";
            infix += needParens1 ? "(" + operand1 + ")" : operand1;
            infix += ch;
            infix += needParens2 ? "(" + operand2 + ")" : operand2;
            
            stack.push(infix);
        }
    }
    
    return stack.top();
}

int main() {
    std::string postfix_expr = "ab+c*";
    std::cout << postfixToInfixOptimized(postfix_expr) << std::endl;  // Output: "(a+b)*c"
    return 0;
}

Code(Java)

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class PostfixToInfixOptimized {
    public static String postfixToInfix(String postfix) {
        Stack<String> stack = new Stack<>();
        
        // Define operator precedence (higher value means higher precedence)
        Map<Character, Integer> precedence = new HashMap<>();
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
        precedence.put('^', 3);
        
        for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            
            // If the character is an operand
            if (Character.isLetterOrDigit(ch)) {
                stack.push(Character.toString(ch));
            }
            // If the character is an operator
            else {
                String operand2 = stack.pop();
                String operand1 = stack.pop();
                
                // Check if operands need parentheses
                boolean needParens1 = false;
                boolean needParens2 = false;
                
                if (operand1.length() > 1 && 
                    precedence.containsKey(operand1.charAt(1)) && 
                    precedence.get(operand1.charAt(1)) < precedence.get(ch)) {
                    needParens1 = true;
                }
                
                if (operand2.length() > 1 && 
                    precedence.containsKey(operand2.charAt(1)) && 
                    precedence.get(operand2.charAt(1)) <= precedence.get(ch)) {
                    needParens2 = true;
                }
                
                // Create the infix expression
                String infix = "";
                infix += needParens1 ? "(" + operand1 + ")" : operand1;
                infix += ch;
                infix += needParens2 ? "(" + operand2 + ")" : operand2;
                
                stack.push(infix);
            }
        }
        
        return stack.peek();
    }
    
    public static void main(String[] args) {
        String postfix_expr = "ab+c*";
        System.out.println(postfixToInfix(postfix_expr));  // Output: "(a+b)*c"
    }
}

Conclusion

Converting a postfix expression to infix is a classic stack-based problem that showcases how this data structure helps manage the order of operations. The brute force approach works well for most cases, while the optimized approach reduces unnecessary parentheses by considering operator precedence.
Both methods have the same time and space complexity of O(n), making them efficient solutions. The key insight is recognizing that postfix notation eliminates the need for parentheses and operator precedence rules during evaluation, but we must reintroduce these elements when converting back to infix notation.
This problem illustrates an important concept in computer science: different notations can represent the same mathematical expression, each with its own advantages for specific purposes. Postfix notation is easier for computers to evaluate, while infix notation is more intuitive for humans to read.

FAQs

Compare

vs InterviewCopilot.io

vs Interviews.chat

vs PrepAI

Resources

Blog

Success Stories

Help Center

Legal

Terms & Conditions

Cookie Policy

GDPR

Postfix to Infix Conversion: Code with Visualization

Problem Statement

Brute Force Approach

Explanation

Code(Python)

Code(C++)

Code(Java)

Optimized Approach

Explanation

Code(Python)

Code(C++)

Code(Java)

Conclusion

FAQs

TAGS

Revolutionizing Interview Preparation with AI