Infix to Prefix Conversion in Java

Last Updated on August 9, 2024 by Abhishek Sharma

Infix to prefix conversion is a fundamental concept in computer science, particularly in the fields of data structures and compilers. In infix notation, operators are placed between operands (e.g., A + B), which is the standard arithmetic expression format. However, computers and certain algorithms find it easier to process expressions in prefix notation, where operators precede their operands (e.g., +AB). Converting infix expressions to prefix form is a common problem that can be efficiently solved using stack-based algorithms. In Java, this conversion process involves handling operators, operands, and parentheses systematically to produce the correct prefix expression. This article explores the methodology and implementation of infix to prefix conversion in Java.

Arithmetic Notations

Different techniques of representing arithmetic statements using symbols and rules are known as arithmetic notations. There are three standard notations for mathematics:
Infix notation: When creating mathematical expressions, infix notation places the operator between the two operands. The expression "3 + 4" is an example of infix notation.
Prefix notation: Polish notation is another name for prefix notation. It doesn’t require brackets and can be assessed without relying on the laws of precedence. Prefix notation, for illustration, is used with the expression "+ 3 4"
Postfix notation: Reverse Polish notation is another name for postfix notation. It doesn’t require brackets and can be assessed without relying on the laws of precedence. The operator follows the operands in postfix notation. In postfix notation, the expression "3 4 +" is an example.

How to Convert Infix to Prefix in Java?

Convert an infix arithmetic expression into an equivalent prefix expression given the infix expression.
The expression will be presented as a string, where the operators are (+, -, *, /) and the operands are alphabetic characters, such as a-z or A-Z. ‘(‘ and ‘)’ are examples of brackets that can be used with expressions.

Sample example :
Input infix expression : a ( b + c + d)
Output prefix expression : a+b+cd
Input infix expression : bc
Output prefix expression : bc

Precedence Order and Associativity of Operators

Infix to Prefix Algorithm

Here,is the infix to prefix algorithm:

• Make an empty output string and empty stack.
• Reverse the infix phrase: All components of the infix expression, including the operands and operators, should be reversed.
• From left to right, iterate through the reversed infix expression.
• Add the current character to the output string if it is an operand (a number or a variable).
• Push the current character onto the stack if it’s a closing ‘)’ bracket.
• Compare the precedence of the current character to that of the operator at the top of the stack if it is an operator or an opening bracket ‘(‘.
• Push the current operator onto the stack if it has higher priority than the operator at the top of the stack or if it contains no other operators.

How to Design Infix to Prefix Algorithm

Dry Run for Infix to Prefix Example

Code Implementation

import java.util.*;

class PrepBytes {
    // Function to check if the character is an operand
    static boolean isalpha(char c)
    {
        if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }

    // Function to check if the character is digit
    static boolean isdigit(char c)
    {
        if (c >= '0' && c <= '9') {
            return true;
        }
        return false;
    }

    // Function to check if the character is an operator
    static boolean isOperator(char c)
    {
        return (!isalpha(c) && !isdigit(c));
    }

    // Function to get priority of operators
    static int getPriority(char C)
    {
        if (C == '-' || C == '+')
            return 1;
        else if (C == '*' || C == '/')
            return 2;
        else if (C == '^')
            return 3;

        return 0;
    }

    // Reverse the letters of the word
    static String reverse(char str[], int start, int end)
    {
        // Temporary variable to store character
        char temp;
        while (start < end) {
            // Swapping the first and last character
            temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
        return String.valueOf(str);
    }

    // Function to convert infix to postfix expression
    static String infixToPostfix(char[] infix1)
    {
        String infix = '(' + String.valueOf(infix1) + ')';

        int l = infix.length();
        Stack<Character> char_stack = new Stack<>();
        String output = "";

        for (int i = 0; i < l; i++) {

            // If the scanned character is an
            // operand, add it to output.
            if (isalpha(infix.charAt(i))
                || isdigit(infix.charAt(i)))
                output += infix.charAt(i);

            // If the scanned character is an
            // ‘(‘, push it to the stack.
            else if (infix.charAt(i) == '(')
                char_stack.add('(');

            // If the scanned character is an
            // ‘)’, pop and output from the stack
            // until an ‘(‘ is encountered.
            else if (infix.charAt(i) == ')') {
                while (char_stack.peek() != '(') {
                    output += char_stack.peek();
                    char_stack.pop();
                }

                // Remove '(' from the stack
                char_stack.pop();
            }

            // Operator found
            else {
                if (isOperator(char_stack.peek())) {
                    while (
                        (getPriority(infix.charAt(i))
                        < getPriority(char_stack.peek()))
                        || (getPriority(infix.charAt(i))
                                <= getPriority(
                                    char_stack.peek())
                            && infix.charAt(i) == '^')) {
                        output += char_stack.peek();
                        char_stack.pop();
                    }

                    // Push current Operator on stack
                    char_stack.add(infix.charAt(i));
                }
            }
        }
        while (!char_stack.empty()) {
            output += char_stack.pop();
        }
        return output;
    }

    static String infixToPrefix(char[] infix)
    {
        // Reverse String and replace ( with ) and vice
        // versa Get Postfix Reverse Postfix
        int l = infix.length;

        // Reverse infix
        String infix1 = reverse(infix, 0, l - 1);
        infix = infix1.toCharArray();

        // Replace ( with ) and vice versa
        for (int i = 0; i < l; i++) {

            if (infix[i] == '(') {
                infix[i] = ')';
                i++;
            }
            else if (infix[i] == ')') {
                infix[i] = '(';
                i++;
            }
        }

        String prefix = infixToPostfix(infix);

        // Reverse postfix
        prefix = reverse(prefix.toCharArray(), 0, l - 1);

        return prefix;
    }

    // Driver code
    public static void main(String[] args)
    {
        String s = ("x+y*z/w+u");

        // Function call
        System.out.print(infixToPrefix(s.toCharArray()));
    }
}

Output
++x/*yzwu

Conclusion
Converting infix expressions to prefix notation in Java requires a clear understanding of operator precedence and associativity, as well as a methodical approach to handling parentheses and stack operations. Mastering this conversion process is crucial for applications in compilers, expression evaluation, and other areas where expression parsing is necessary. By implementing the infix to prefix conversion in Java, you can deepen your understanding of both data structures and algorithmic thinking, which are vital skills for any software developer.

FAQs related to Infix to Prefix Conversion in Java

Here are some FAQs related to Infix to Prefix Conversion in Java:

Q1: What is the main difference between infix and prefix notation?
A1: In infix notation, operators are placed between operands (e.g., A + B), while in prefix notation, operators precede their operands (e.g., +AB). Prefix notation is also known as Polish notation.

Q2: Why is prefix notation preferred in certain computational scenarios?
A2: Prefix notation eliminates the need for parentheses to define the order of operations, making it easier for computers to parse and evaluate expressions without ambiguity.

Q3: What is the role of a stack in infix to prefix conversion?
A3: A stack is used to temporarily hold operators and manage their precedence and associativity during the conversion process, ensuring that the final prefix expression is correctly formatted.

Q4: Can the same algorithm be used to convert infix to postfix notation?
A4: Yes, the algorithm for infix to postfix conversion is similar but involves different placement of operators relative to operands. While both conversions use a stack, the steps differ slightly to account for the different notations.

Q5: How does Java handle operator precedence and associativity during the conversion?
A5: In Java, operator precedence and associativity are managed by the algorithm through conditional checks during the conversion process, ensuring that operators are placed in the correct order in the prefix expression.