Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Infix to Postfix Conversion

Problem Statement

Write a Java program that converts an infix expression (e.g., "A + B * C") to its postfix equivalent (e.g., "A B C * +") using a stack. The program should handle operators (+, -, *, /) and parentheses, pushing operators onto the stack based on precedence and popping them to the output when appropriate. Test the implementation with at least three different expressions, including simple expressions, expressions with parentheses, and complex expressions with multiple operators. You can visualize this as rearranging a mathematical sentence so that the operations are performed in the correct order without needing parentheses, like organizing tasks in a queue where the work gets done step by step.

Input: A string representing an infix expression (e.g., "A + B * C", "(A + B) * C"). Output: A string representing the postfix expression (e.g., "A B C * +", "A B + C *"). Constraints:

  • The input string length is between 0 and 10^5.
  • The string contains operands (single letters A-Z), operators (+, -, *, /), parentheses (()), and spaces.
  • The input may be empty, null, or invalid (handled gracefully). Example:
  • Input: "A + B * C"
  • Output: "A B C * +"
  • Explanation: * has higher precedence than +, so B * C is processed first, resulting in A B C * +.
  • Input: "(A + B) * C"
  • Output: "A B + C *"
  • Explanation: Parentheses ensure A + B is evaluated first, then multiplied by C.
  • Input: "A + B - C"
  • Output: "A B + C -"
  • Explanation: Operators + and - have equal precedence, processed left to right.

Pseudocode

CLASS CharStack
    SET array to new character array of size 1000
    SET top to -1
    
    FUNCTION push(char)
        IF top equals array length - 1 THEN
            RETURN false
        ENDIF
        INCREMENT top
        SET array[top] to char
        RETURN true
    ENDFUNCTION
    
    FUNCTION pop()
        IF top equals -1 THEN
            RETURN null
        ENDIF
        SET char to array[top]
        DECREMENT top
        RETURN char
    ENDFUNCTION
    
    FUNCTION peek()
        IF top equals -1 THEN
            RETURN null
        ENDIF
        RETURN array[top]
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN top equals -1
    ENDFUNCTION
ENDCLASS

FUNCTION getPrecedence(operator)
    IF operator is '*' or '/' THEN
        RETURN 2
    ELSE IF operator is '+' or '-' THEN
        RETURN 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

FUNCTION infixToPostfix(expression)
    IF expression is null or empty THEN
        RETURN empty string
    ENDIF
    CREATE stack as new CharStack
    CREATE result as new StringBuilder
    FOR each char in expression
        IF char is letter THEN
            APPEND char to result
        ELSE IF char is '(' THEN
            PUSH char to stack
        ELSE IF char is ')' THEN
            WHILE stack is not empty and stack.peek() is not '('
                APPEND stack.pop() to result
            ENDWHILE
            IF stack is not empty THEN
                POP '(' from stack
            ENDIF
        ELSE IF char is operator (+, -, *, /) THEN
            WHILE stack is not empty and stack.peek() is not '(' and getPrecedence(stack.peek()) >= getPrecedence(char)
                APPEND stack.pop() to result
            ENDWHILE
            PUSH char to stack
        ENDIF
    ENDFOR
    WHILE stack is not empty
        APPEND stack.pop() to result
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testExpressions to array of infix expressions
    FOR each expression in testExpressions
        PRINT input expression
        CALL infixToPostfix(expression)
        PRINT postfix result
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a CharStack class with methods: push, pop, peek, isEmpty.
  2. Define a getPrecedence function to return operator precedence: 2 for *, /; 1 for +, -; 0 for others.
  3. In the infixToPostfix method: a. If the input is null or empty, return an empty string. b. Create a stack for operators and a StringBuilder for the result. c. For each character in the expression:
    • If it’s a letter (operand), append it to the result.
    • If it’s '(', push it to the stack.
    • If it’s ')', pop operators from the stack to the result until '(' is found, then pop '('.
    • If it’s an operator, pop higher or equal precedence operators from the stack to the result, then push the current operator. d. After processing, pop remaining operators from the stack to the result. e. Return the result as a string.
  4. In the main method, test with at least three expressions, including simple, parenthesized, and complex cases.

Java Implementation

public class InfixToPostfixConversion {
    // Custom stack implementation for characters
    static class CharStack {
        private char[] array;
        private int top;
        private static final int DEFAULT_SIZE = 1000;

        public CharStack() {
            array = new char[DEFAULT_SIZE];
            top = -1;
        }

        public boolean push(char c) {
            if (top == array.length - 1) {
                return false; // Stack full
            }
            array[++top] = c;
            return true;
        }

        public Character pop() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top--];
        }

        public Character peek() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top];
        }

        public boolean isEmpty() {
            return top == -1;
        }
    }

    // Returns precedence of operators
    private int getPrecedence(char operator) {
        if (operator == '*' || operator == '/') {
            return 2;
        } else if (operator == '+' || operator == '-') {
            return 1;
        }
        return 0;
    }

    // Converts infix expression to postfix
    public String infixToPostfix(String expression) {
        if (expression == null || expression.isEmpty()) {
            return "";
        }
        CharStack stack = new CharStack();
        StringBuilder result = new StringBuilder();

        for (char c : expression.replaceAll("\\s", "").toCharArray()) {
            if (Character.isLetter(c)) {
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                if (!stack.isEmpty()) {
                    stack.pop(); // Remove '('
                }
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!stack.isEmpty() && stack.peek() != '(' && 
                       getPrecedence(stack.peek()) >= getPrecedence(c)) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    // Main method to test infix to postfix conversion
    public static void main(String[] args) {
        InfixToPostfixConversion converter = new InfixToPostfixConversion();

        // Test cases
        String[] testExpressions = {
            "A + B * C",          // Simple expression
            "(A + B) * C",        // Expression with parentheses
            "A + B * C - D / E",  // Complex expression
            "",                   // Empty string
            "X * (Y + Z)"        // Nested parentheses
        };

        for (int i = 0; i < testExpressions.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Infix: \"" + testExpressions[i] + "\"");
            String result = converter.infixToPostfix(testExpressions[i]);
            System.out.println("Postfix: \"" + result + "\"\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Infix: "A + B * C"
Postfix: "ABC*+"

Test case 2:
Infix: "(A + B) * C"
Postfix: "AB+C*"

Test case 3:
Infix: "A + B * C - D / E"
Postfix: "ABC*+DE/-"

Test case 4:
Infix: ""
Postfix: ""

Test case 5:
Infix: "X * (Y + Z)"
Postfix: "XYZ+*"

Explanation:

  • Test case 1: "A + B * C" → * has higher precedence, so B * C becomes "BC*", then + gives "ABC*+".
  • Test case 2: "(A + B) * C" → Parentheses prioritize A + B, giving "AB+", then * gives "AB+C*".
  • Test case 3: "A + B * C - D / E" → * and / have higher precedence, processed left to right, then + and -, giving "ABC*+DE/-".
  • Test case 4: "" → Empty input returns empty string.
  • Test case 5: "X * (Y + Z)" → Parentheses prioritize Y + Z, giving "YZ+", then * gives "XYZ+*".

How It Works

  • CharStack:
    • Stores operators and parentheses, with methods push, pop, peek, isEmpty.
  • getPrecedence:
    • Assigns precedence: 2 for *, /; 1 for +, -; 0 for others.
  • infixToPostfix:
    • Outputs operands (letters) directly to the result.
    • Pushes '(' to stack, pops operators until ')' for closing parentheses.
    • For operators, pops higher/equal precedence operators, then pushes current operator.
    • Pops remaining operators at the end.
  • Example Trace (Test case 1):
    • Input: "A + B * C".
    • A: Append to result → "A".
    • +: Push to stack → [+].
    • B: Append to result → "AB".
    • *: Higher precedence than +, push → [+, *].
    • C: Append to result → "ABC".
    • End: Pop * → "ABC*", pop + → "ABC*+".
  • Main Method: Tests simple, parenthesized, complex, empty, and nested expressions.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Push/Pop/PeekO(1)O(1)
Full AlgorithmO(n)O(n)

Note:

  • n is the length of the input expression.
  • Time complexity: O(n) for iterating through the expression, with O(1) for each stack operation.
  • Space complexity: O(n) for the stack (worst case: all operators/parentheses) and StringBuilder.
  • Worst case: O(n) time and O(n) space for expressions like "((A+B)*C)".

✅ Tip: Use a stack to manage operator precedence in infix-to-postfix conversion, as it naturally handles the order of operations. Test with parentheses and multiple operator types to ensure correctness.

⚠ Warning: Handle invalid inputs (e.g., unbalanced parentheses) gracefully to avoid stack underflow. Remove spaces from the input to simplify processing.