Infix to Postfix
SatvikMPatil
3781
StringStackLeetCodeInterview

Infix to Postfix Conversion in Java

In this guide, we’ll learn how to convert an infix expression (like a+bc) to a postfix expression (like abc+) using Java. This explanation is simple and easy to understand for everyone, even beginners.

Rules for Infix to Postfix Conversion

  • Operands (like a, b) go directly to the output.
  • Operators (+, -, *, /, ^) are pushed to a stack based on their precedence: +, - (low), *, / (medium), ^ (high).
  • Parentheses: Push ( onto the stack and pop operators until ( is found when ) is encountered.
  • At the end, pop all remaining operators from the stack to the output.
    image

Program Breakdown
Here’s how the program works step-by-step:

  • Check each character in the input.
  • If it’s an operand, print it.
  • If it’s (, push it to the stack.
  • If it’s ), pop operators until ( is found.
  • If it’s an operator, compare its precedence with the operator on top of the stack.
  • At the end, pop any operators left in the stack and add them to the output.

Code

import java.util.Scanner;
import java.util.Stack;

class Main {

    // Check if a character is an operand (alphabetic character)
    public static boolean isOperand(char character) {
        return (character >= 'a' && character <= 'z');
    }

    // Get the precedence of an operator
    public static int getPrecedence(char operator) {
        if (operator == '+' || operator == '-') {
            return 1; // Lowest precedence
        } else if (operator == '*' || operator == '/') {
            return 2; // Medium precedence
        } else if (operator == '^') {
            return 3; // Highest precedence
        }
        return -1; // Non-operator characters
    }

    // Convert infix expression to postfix
    public static void convertToPostfix(String infixExpression) {
        Stack<Character> operatorStack = new Stack<>();

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

            // If the character is an operand, print it directly
            if (isOperand(currentChar)) {
                System.out.print(currentChar);
            } 
            // Handle opening parenthesis
            else if (currentChar == '(') {
                operatorStack.push(currentChar);
            } 
            // Handle closing parenthesis
            else if (currentChar == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    System.out.print(operatorStack.pop());
                }
                operatorStack.pop(); // Remove '(' from the stack
            } 
            // Handle operators
            else {
                while (!operatorStack.isEmpty() && getPrecedence(operatorStack.peek()) >= getPrecedence(currentChar)) {
                    System.out.print(operatorStack.pop());
                }
                operatorStack.push(currentChar);
            }
        }

        // Pop all remaining operators from the stack
        while (!operatorStack.isEmpty()) {
            System.out.print(operatorStack.pop());
        }
    }

    public static void main(String[] args) {
        System.out.println("Enter the infix expression:");
        Scanner scanner = new Scanner(System.in);
        String infixExpression = scanner.nextLine();
        System.out.print("Postfix expression: ");
        convertToPostfix(infixExpression);
    }
}

Output

Enter the infix expression: a+b*(c^d-e)
Postfix expression: abcd^e-*+

Example
Input: (a+b)c
Steps:

  • In the example (a+b)*c, ( is pushed to the stack. Then a is added to the output, followed by pushing + to the stack and adding b to the output. When ) is encountered, + is popped and added to the output. Then * is pushed to the stack, and c is added to the output. Finally, * is popped and added to the output, giving the postfix expression ab+c*.

Output: ab+c*

Conclusion
This simple Java program helps you easily convert infix expressions to postfix. Mastering this concept is a great step toward understanding how calculators and compilers process expressions.

Comments (4)