Master Infix, Prefix, Postfix Conversions with Java

🚀 Introduction

Welcome to Day 64 of my DSA Journey!
After solving around 30 practice problems on Linked Lists, I’ve moved on to another fundamental and highly useful data structure in problem-solving — Stacks & Queues.

Over the past 3 days, I explored one of the most important topics in this area: Prefix, Infix, and Postfix conversions.
This included not only learning the conversion techniques but also revisiting the basics of expressions such as operators, operands, precedence, and associativity.

I’m documenting this journey publicly to stay consistent, track my progress, and also help others who are beginning their DSA preparation from scratch.

👉 You can also follow me on Twitter where I share real-time updates, problem breakdowns, and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 61

Operators and Operands
Operator Precedence & Associativity
Types of Expressions
Why Prefix and Postfix?
Infix → Postfix Conversion
Infix → Prefix Conversion

Day 62

Postfix → Infix Conversion
Prefix → Infix Conversion

Day 63

Postfix → Prefix Conversion
Prefix → Postfix Conversion

Now, let’s dive deeper into each of these concepts 👇

1. Fundamentals

Before diving into infix, prefix, and postfix conversions, it’s important to strengthen the basics of expressions. These fundamentals form the backbone of conversion rules and evaluation using stacks.

Operands and Operators:

Operand → The values on which operations are performed.
Example: In A + B, A and B are operands.
Operator → The symbols that perform operations on operands.
Example: In A + B, the symbol + is an operator.

Operators can be of different types:

Arithmetic Operators: +, -, *, /, %
Relational Operators: <, >, <=, >=
Logical Operators: &&, ||, !
Bitwise Operators: &, |, ^, ~

Operator Precedence & Associativity:

When multiple operators appear in an expression, precedence decides which operator executes first, and associativity decides execution order when operators have the same precedence.

Example:
Expression → A + B * C

Here, * has higher precedence than +.
So, B * C is evaluated first, then added to A.

Associativity Example:
Expression → A - B - C

Both operators have the same precedence.
Associativity of - is Left to Right, so it becomes (A - B) - C.

Operator	Precedence	Associativity
`*`, `/`, `%`	High	Left → Right
`+`, `-`	Medium	Left → Right
`=`	Low	Right → Left

Types of Expressions:

Infix Expression → Operator is between operands.
Example: A + B
Prefix Expression (Polish Notation) → Operator is before operands.
Example: + A B
Postfix Expression (Reverse Polish Notation) → Operator is after operands.
Example: A B +

Why Prefix and Postfix?

At first glance, infix expressions feel natural because they’re how we usually write equations in mathematics.
But the problem with infix is:

It requires parentheses to resolve ambiguity.
It requires complex parsing to respect precedence and associativity.

On the other hand:

Prefix and Postfix expressions completely eliminate the need for parentheses.
Their evaluation is straightforward using a stack.

For example:

Infix: (A + B) * C
Prefix: * + A B C
Postfix: A B + C *

Here, both prefix and postfix clearly represent the order of execution without needing brackets.

2. Infix → Postfix Conversion

Convert a standard infix expression (operators between operands) into a postfix expression (operators after operands) so it can be evaluated easily using a stack without worrying about parentheses, precedence or associativity during evaluation.

Example:

Infix: a + b * ( c ^ d - e )

Postfix: abcd^e-*+

Explanation:

c ^ d evaluated first → cd^
then cd^ - e → cd^ e - → cd^e-
then b * (cd^e-) → b cd^e- * → bcd^e-*
finally a + ... → a bcd^e-* + → abcd^e-*+.

Rules of Conversion:

Operands (letters/digits) → append directly to the output (postfix).
Left parenthesis (() → push onto stack.
Right parenthesis ()) → pop from stack and append to output until a left parenthesis ( is found; discard both parentheses.
Operators (+, -, *, /, %, ^, ...):
- While stack is not empty and
  - current operator has lower precedence than operator at stack top, or
  - current operator has equal precedence and is left-associative (i.e., not ^ in our implementation),
- pop from stack and append to output.
- Push the current operator.
After processing the whole input, pop any remaining operators from the stack to the output.

Precedence used in code (high → low):

^ : 3 (right-associative)
*, /, % : 2 (left-associative)
+, - : 1 (left-associative)

Code Implementation:

public class InfixToPostfix {
    public static String infixToPostfix(String str){
        int i=0;
        StringBuilder postfix= new StringBuilder();
        Stack<Character> st = new Stack<>();

        while (i < str.length()){
            char ch = str.charAt(i);
            if((ch >= 'A' && ch <='Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')){
                postfix.append(ch);
            } else if(ch == '('){
                st.push(ch);
            } else if(ch == ')'){
                while (!st.isEmpty() && st.peek() != '('){
                    postfix.append(st.pop());
                }
                if(!st.isEmpty() && st.peek() == '('){
                    st.pop();
                }
            } else {
                while(!st.isEmpty() && ((priority(ch) < priority(st.peek())) || ((priority(ch) == priority(st.peek())) && ch != '^'))){
                    postfix.append(st.pop());
                }
                st.push(ch);
            }

            i++;
        }

        while (!st.isEmpty()){
            postfix.append(st.pop());
        }

        return postfix.toString();
    }

    private static int priority(char op){
        if(op == '^'){
            return 3;
        }
        if(op == '*' || op == '/' || op == '%'){
            return 2;
        }
        if(op == '+' || op == '-'){
            return 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        String str = "a+b*(c^d-e)";

        String ans = infixToPostfix(str);
        System.out.println(ans);
    }
}

Key Notes:

Operands are assumed to be single alphanumeric characters (letters or digits).
The priority function returns integer precedence.
The while condition for operators handles left vs right associativity: ^ is treated as right-associative (so it is not popped on equal precedence).

Time & Space Complexity:

Time Complexity: O(n) — each character is processed once; each operator is pushed/popped at most once.
Space Complexity: O(n) — stack may store up to O(n) operators/parentheses; output also of size O(n).

3. Infix → Prefix Conversion

Infix to Prefix conversion is a method to convert a standard infix expression (operators between operands) into a prefix expression (operators before operands). This allows easy evaluation using a stack without worrying about parentheses, precedence, or associativity during evaluation.

The key trick: reverse the expression, swap brackets, convert to postfix, then reverse again to get the prefix expression.

Example:

Infix: (A + B) * C - D + F

Prefix: + - * + A B C D F

Explanation:

Reverse the infix and swap brackets → F + D - C * ( B + A )
Convert this modified expression to postfix → F D C B A + * - +
Reverse again to get the prefix → + - * + A B C D F

Rules of Conversion:

Reverse the input string and swap ( ↔ ).
Convert the reversed string to postfix using a stack:
- Operands → append directly to the output.
- Left parenthesis (() → push onto stack.
- Right parenthesis ()) → pop from stack until a left parenthesis ( is found; discard both parentheses.
- Operators (+, -, *, /, %, ^) →
  - While stack is not empty and
    - current operator has lower precedence than stack top, or
    - current operator has equal precedence and is right-associative (^),
  - pop from stack and append to output.
  - Push the current operator.
After processing the whole input, pop any remaining operators from the stack to the output.
Reverse the postfix output and swap brackets to get the prefix expression.

Precedence used in code (high → low):

^ : 3 (right-associative)
*, /, % : 2 (left-associative)
+, - : 1 (left-associative)

Code Implementation:

public class InfixToPrefix {
    public static String infixToPrefix(String str) {
        str = reverseAndSwapBracket(str);

        String prefix = convertInfixToPostfix(str);

        return reverseAndSwapBracket(prefix);
    }

    private static String convertInfixToPostfix(String str) {
        int i=0;
        StringBuilder postfix= new StringBuilder();
        Stack<Character> st = new Stack<>();

        while (i < str.length()){
            char ch = str.charAt(i);
            if((ch >= 'A' && ch <='Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')){
                postfix.append(ch);
            } else if(ch == '('){
                st.push(ch);
            } else if(ch == ')'){
                while (!st.isEmpty() && st.peek() != '('){
                    postfix.append(st.pop());
                }
                if(!st.isEmpty() && st.peek() == '('){
                    st.pop();
                }
            } else {
                while(!st.isEmpty() && ((priority(ch) < priority(st.peek())) || ((priority(ch) == priority(st.peek())) && ch == '^'))){
                    postfix.append(st.pop());
                }
                st.push(ch);
            }

            i++;
        }

        while (!st.isEmpty()){
            postfix.append(st.pop());
        }

        return postfix.toString();
    }

    private static int priority(char op){
        if(op == '^'){
            return 3;
        }
        if(op == '*' || op == '/' || op == '%'){
            return 2;
        }
        if(op == '+' || op == '-'){
            return 1;
        }

        return -1;
    }

    private static String reverseAndSwapBracket(String str) {
        char[] arr = str.toCharArray();
        int start = 0;
        int end = arr.length-1;

        // Reverse
        while (start < end) {
            char left = swapBrackets(arr[start]);
            char right = swapBrackets(arr[end]);

            arr[start] = right;
            arr[end] = left;

            start++;
            end--;
        }

        // If odd length, swap middle char as well
        if (start == end) {
            arr[start] = swapBrackets(arr[start]);
        }

        return new String(arr);
    }

    private static char swapBrackets(char ch) {
        if(ch == '(') return ')';
        else if(ch == ')') return '(';

        return ch;
    }

    public static void main(String[] args) {
        String str = "(A+B)*C-D+F";

        String ans = infixToPrefix(str);
        System.out.println(ans);
    }
}

infixToPrefix(str): Main function that orchestrates the conversion.
reverseAndSwapBracket(str): Reverses the string and swaps parentheses.
convertInfixToPostfix(str): Converts the modified infix to postfix using a stack.
priority(op): Returns the precedence of an operator.
swapBrackets(ch): Helper to swap ( and ) during reversal.

Key Notes:

Reversal simplifies handling the right-associativity of operators like ^.
Parentheses are handled automatically by reversing and swapping them.
Operands are assumed to be single characters (letters or digits).
The same stack-based approach as infix → postfix ensures correctness and efficiency.

Time & Space Complexity:

Time Complexity: O(n) — each character is processed once; operators are pushed/popped at most once.
Space Complexity: O(n) — stack stores operators/parentheses; output stores n characters.

4. Postfix → Infix Conversion

Converting a postfix expression (operators after operands) into an infix expression (operators between operands) can be done efficiently using a stack.

This approach ensures that the original order of operations is preserved and parentheses are added to maintain clarity.

Example:

Postfix: AB-DE+F*/
Infix: ((A*(B-D))+E)/F)

Rules of Conversion:

Initialize an empty stack.
Traverse the postfix expression from left to right.
For each character in the expression:
- Operand → Push it as a string onto the stack.
- Operator → Pop two elements from the stack, say firstTop and secondTop.
  - Combine them as (secondTop operator firstTop) and push the result back onto the stack.
After traversing the entire expression, the stack will contain the complete infix expression.

Code Implementation:

public class PostfixToInfix {
    public static String postfixToInfix(String str) {
        int i = 0;
        Stack<String> st = new Stack<>();

        while (i < str.length()) {
            char ch = str.charAt(i);
            if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
                st.push(ch + "");
            } else {
                String firstTop = st.pop();
                String secondTop = st.pop();
                String res = "(" + secondTop + ch + firstTop + ")";
                st.push(res);
            }
            i++;
        }

        return st.pop();
    }

    public static void main(String[] args) {
        String str = "AB-DE+F*/";
        String ans = postfixToInfix(str);
        System.out.println(ans);
    }
}

Key Notes:

Operands are assumed to be single characters (letters or digits).
Each operator always combines the last two operands popped from the stack.
Parentheses are automatically added to maintain correct order of operations.
The stack ensures that the expression is reconstructed correctly even for complex postfix expressions.

Time & Space Complexity:

Time Complexity: O(n) — each character is processed once.
Space Complexity: O(n) — the stack stores at most n/2 intermediate expressions during traversal.

5. Prefix → Infix Conversion

Converting a prefix expression (operators before operands) into an infix expression (operators between operands) can be efficiently done using a stack.

This approach ensures that the original order of operations is preserved, and parentheses are added to maintain clarity.

Example:

Prefix: *+PQ-MN
Infix: ((P+Q)*(M-N))

Rules of Conversion:

Initialize an empty stack.
Traverse the prefix expression from right to left.
For each character in the expression:
- Operand → Push it as a string onto the stack.
- Operator → Pop two elements from the stack, say firstTop and secondTop.
  - Combine them as (firstTop operator secondTop) and push the result back onto the stack.
After traversing the entire expression, the stack will contain the complete infix expression.

Code Implementation:

public class PrefixToInfix {
    public static String prefixToInfix(String str) {
        int i = str.length() - 1;
        Stack<String> st = new Stack<>();

        while (i >= 0) {
            char ch = str.charAt(i);
            if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
                st.push(ch + "");
            } else {
                String firstTop = st.pop();
                String secondTop = st.pop();
                String res = "(" + firstTop + ch + secondTop + ")";
                st.push(res);
            }
            i--;
        }

        return st.pop();
    }

    public static void main(String[] args) {
        String str = "*+PQ-MN";
        String ans = prefixToInfix(str);
        System.out.println(ans);  // Output: ((P+Q)*(M-N))
    }
}

Key Notes:

Operands are assumed to be single characters (letters or digits).
Each operator always combines the first two operands popped from the stack when traversing right to left.
Parentheses are automatically added to maintain correct order of operations.
The stack ensures the expression is reconstructed correctly even for complex prefix expressions.

Time & Space Complexity:

Time Complexity: O(n) — each character is processed once.
Space Complexity: O(n) — the stack stores at most n/2 intermediate expressions during traversal.

6. Postfix → Prefix Conversion

Converting a postfix expression (operators after operands) into a prefix expression (operators before operands) can be efficiently done using a stack.

This approach preserves the original order of operations and reconstructs the expression in prefix form.

Example:

Postfix: AB-DE+F*/
Prefix: /*A+BD-EF

Rules of Conversion:

Initialize an empty stack.
Traverse the postfix expression from left to right.
For each character in the expression:
- Operand → Push it as a string onto the stack.
- Operator → Pop two elements from the stack, say firstTop and secondTop.
  - Combine them as (operator + secondTop + firstTop) and push the result back onto the stack.
After traversing the entire expression, the stack will contain the complete prefix expression.

Code Implementation:

public class PostfixToPrefix {
    public static String postfixToPrefix(String str) {
        int i = 0;
        Stack<String> st = new Stack<>();

        while (i < str.length()) {
            char ch = str.charAt(i);
            if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
                st.push(ch + "");
            } else {
                String firstTop = st.pop();
                String secondTop = st.pop();
                String res = ch + secondTop + firstTop;
                st.push(res);
            }
            i++;
        }

        return st.pop();
    }

    public static void main(String[] args) {
        String str = "AB-DE+F*/";
        String ans = postfixToPrefix(str);
        System.out.println(ans);  // Output: /*A+BD-EF
    }
}

Key Notes:

Operands are assumed to be single characters (letters or digits).
Each operator always combines the last two operands popped from the stack.
The operator is placed before the two operands to form the prefix expression.
The stack ensures that the expression is reconstructed correctly even for complex postfix expressions.

Time & Space Complexity:

Time Complexity: O(n) — each character is processed once.
Space Complexity: O(n) — the stack stores at most n/2 intermediate expressions during traversal.

7. Prefix → Postfix Conversion

Converting a prefix expression (operators before operands) into a postfix expression (operators after operands) can be efficiently done using a stack.

This approach preserves the original order of operations and reconstructs the expression in postfix form.

Example:

Prefix: /-AB*+DEF
Postfix: AB-+DE*F/

Rules of Conversion:

Initialize an empty stack.
Traverse the prefix expression from right to left.
For each character in the expression:
- Operand → Push it as a string onto the stack.
- Operator → Pop two elements from the stack, say firstTop and secondTop.
  - Combine them as (firstTop + secondTop + operator) and push the result back onto the stack.
After traversing the entire expression, the stack will contain the complete postfix expression.

Code Implementation:

public class PrefixToPostfix {
    public static String prefixToPostfix(String str) {
        int i = str.length() - 1;
        Stack<String> st = new Stack<>();

        while (i >= 0) {
            char ch = str.charAt(i);
            if ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
                st.push(ch + "");
            } else {
                String firstTop = st.pop();
                String secondTop = st.pop();
                String res = firstTop + secondTop + ch;
                st.push(res);
            }
            i--;
        }

        return st.pop();
    }

    public static void main(String[] args) {
        String str = "/-AB*+DEF";
        String ans = prefixToPostfix(str);
        System.out.println(ans);  // Output: AB-+DE*F/
    }
}

Key Notes

Operands are assumed to be single characters (letters or digits).
Each operator always combines the first two operands popped from the stack when traversing right to left.
The operator is placed after the two operands to form the postfix expression.
The stack ensures that the expression is reconstructed correctly even for complex prefix expressions.

Time & Space Complexity

Time Complexity: O(n) — each character is processed once.
Space Complexity: O(n) — the stack stores at most n/2 intermediate expressions during traversal.

8. What's next

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

Posting new blog updates every 3 days to share what I’m learning and building.
Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

9. Conclusion

Over the past few days, I dedicated my time to exploring expression conversions — tackling infix, prefix, and postfix transformations in all directions.

Here’s what I personally learned from this journey:

Stacks are powerful: They simplify expression evaluation and conversions by efficiently managing operands and operators.
Operator precedence & associativity matter: Understanding these helped me implement conversions correctly and avoid common mistakes.
Prefix & Postfix expressions are evaluation-friendly: Seeing how they remove parentheses and allow straightforward computation gave me a new perspective on problem-solving.
Step-by-step practice works: Breaking down each conversion into rules, working through examples, and coding them solidified my understanding.

Through this process, I strengthened my DSA fundamentals, gained confidence in handling complex expression problems, and improved both problem-solving skills and coding efficiency.

👉 For anyone on a similar journey: stay consistent, code daily, and embrace challenging problems — every small step compounds into real progress.

Thanks for reading! 🙌
Follow me here (and on Twitter) for more updates as I continue my DSA journey 🚀.

Command Palette

🚀 Introduction

📅 Here’s What I Covered Over the Last 3 Days:

1. Fundamentals

Operands and Operators:

Operator Precedence & Associativity:

Types of Expressions:

Why Prefix and Postfix?

2. Infix → Postfix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes:

Time & Space Complexity:

3. Infix → Prefix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes:

Time & Space Complexity:

4. Postfix → Infix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes:

Time & Space Complexity:

5. Prefix → Infix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes:

Time & Space Complexity:

6. Postfix → Prefix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes:

Time & Space Complexity:

7. Prefix → Postfix Conversion

Example:

Rules of Conversion:

Code Implementation:

Key Notes

Time & Space Complexity

8. What's next

9. Conclusion

Comments

More from this blog