DSF, Snippets

Java Program to Convert Infix Notation to PostFix Notation

1 Comment

Infix notation is the standard way we write arithmetic expressions, with operators between operands — e.g., A + B. Postfix notation (also called Reverse Polish Notation or RPN) places operators after their operands — e.g., A B +. Postfix expressions can be evaluated by machines without needing parentheses or operator-precedence rules, making them ideal for expression evaluators and compilers.

In this post, we implement a Java program that converts an infix expression to its equivalent postfix form using a character stack and an operator-precedence table.

Conversion Algorithm

  1. Scan the infix expression left to right, one character at a time.
  2. If the character is an operand, append it directly to the postfix output.
  3. If the character is an open bracket (, push it onto the stack.
  4. If the character is an operator, pop all operators from the stack with higher or equal precedence and append them to output, then push the current operator.
  5. If the character is a close bracket ), pop operators from the stack and append them to output until an open bracket ( is found; discard the brackets.
  6. At the end, pop and append any remaining operators on the stack.

Java Program: Infix to Postfix Conversion

import java.io.*;
import java.lang.*;

// Character stack used to hold operators during conversion
class OperatorStack {
    private static final int STACK_SIZE = 50;
    private int top;
    private char items[];

    public OperatorStack() {
        top = -1;
        items = new char[STACK_SIZE];
    }

    // Pushes an operator or bracket onto the stack
    public void push(char operator) {
        if (top == STACK_SIZE - 1) {
            System.out.println("Stack overflow");
            return;
        }
        top++;
        items[top] = operator;
    }

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

    public char pop() {
        if (top == -1) {
            System.out.println("Stack is empty - cannot pop");
            return ' ';
        }
        return items[top--];
    }

    public char peek() {
        if (top == -1) {
            System.out.println("Stack is empty - cannot peek");
            return ' ';
        }
        return items[top];
    }
}

// Converts an infix expression string to its postfix equivalent
class InfixToPostfixConverter {

    private boolean isOpenBracket(char ch) {
        return ch == '(';
    }

    private boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '/' || ch == '*';
    }

    // Returns true if the character is a letter or digit (an operand)
    private boolean isOperand(char ch) {
        return (ch >= '0' && ch <= '9')
            || (ch >= 'a' && ch <= 'z')
            || (ch >= 'A' && ch <= 'Z');
    }

    // Returns a numeric precedence value; higher number = higher precedence
    private int precedence(char operator) {
        switch (operator) {
            case '+': return 2;
            case '-': return 2;
            case '*': return 4;
            case '/': return 3;
            case '%': return 1;
            default:  return 0;
        }
    }

    // Converts the given infix expression to postfix and prints the result
    public void convert(String infixExpression) {
        OperatorStack stack = new OperatorStack();
        int outputIndex = 0;
        char[] postfixOutput = new char[infixExpression.length()];

        for (int i = 0; i < infixExpression.length(); i++) {
            char currentChar = infixExpression.charAt(i);

            if (isOpenBracket(currentChar)) {
                stack.push(currentChar);

            } else if (isOperand(currentChar)) {
                postfixOutput[outputIndex++] = currentChar;

            } else if (isOperator(currentChar)) {
                if (stack.isEmpty()) {
                    stack.push(currentChar);
                } else {
                    if (precedence(currentChar) >= precedence(stack.peek())) {
                        stack.push(currentChar);
                    } else {
                        while (!stack.isEmpty()
                                && precedence(currentChar) < precedence(stack.peek())) {
                            postfixOutput[outputIndex++] = stack.pop();
                        }
                        stack.push(currentChar);
                    }
                }
            } else if (!isOpenBracket(currentChar)) {
                // Closing bracket: pop and output until matching '(' found
                while (!stack.isEmpty() && !isOpenBracket(stack.peek())) {
                    postfixOutput[outputIndex++] = stack.pop();
                }
                if (!stack.isEmpty() && isOpenBracket(stack.peek())) {
                    stack.pop();  // Discard the '('
                }
            }
        }

        // Pop any remaining operators
        while (!stack.isEmpty()) {
            postfixOutput[outputIndex++] = stack.pop();
        }

        System.out.print("Postfix: ");
        for (int i = 0; i < infixExpression.length(); i++) {
            System.out.print(postfixOutput[i]);
        }
        System.out.println();
    }
}

public class InfixToPostfix {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter an expression in infix notation:");
        String infixExpression = reader.readLine();
        InfixToPostfixConverter converter = new InfixToPostfixConverter();
        converter.convert(infixExpression);
    }
}

How the Code Works

  1. OperatorStack — A fixed-size character stack for holding operators and open brackets during conversion.
  2. isOperand() — Checks if a character is a letter or digit, meaning it should go directly to the output.
  3. precedence() — Returns a numeric rank for each operator. * outranks / outranks +/-. This table drives the ordering decisions.
  4. Operator handling — If the incoming operator’s precedence is lower than the top of the stack, higher-precedence operators are popped and sent to output first.
  5. Bracket handling — Open brackets are pushed and act as a barrier. When a closing bracket is encountered, operators are popped until the matching open bracket is found and discarded.
  6. Flush — After the full expression is scanned, any operators remaining on the stack are appended to the output.

Sample Output

Enter an expression in infix notation:
(A+B)*(C+D)
Postfix: AB+CD+*

Enter an expression in infix notation:
(A/B)*(C/D)
Postfix: AB/CD/*

Output Explanation

  • (A+B)*(C+D) → AB+CD+* — A and B go to output, then + is popped after the bracket closes (AB+). Same for C+D → CD+. Finally the outer * is appended: AB+CD+*.
  • (A/B)*(C/D) → AB/CD/* — Same pattern: each sub-expression is fully converted before the outer * is added.

See Also

Conclusion

Converting infix to postfix is a classic application of the stack data structure. The algorithm elegantly handles operator precedence and parentheses in a single left-to-right scan, producing an expression that can be evaluated without any precedence lookups. This same logic is used in expression parsers inside compilers, spreadsheet engines, and calculators.

One thought on “Java Program to Convert Infix Notation to PostFix Notation”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.