Infix to Prefix Conversion in Java

Last Updated on May 31, 2023 by Mayank Dham

This article explores the concept of converting infix expressions to prefix notation, focusing on the implementation in Java. By understanding this conversion process, developers can unlock powerful techniques to simplify expression parsing and evaluation in their Java programs.

In this article, we will delve into the fundamentals of infix and prefix notations, highlighting their differences and advantages. We will then explore various algorithms and data structures commonly employed to convert infix expressions to prefix notation. Throughout the discussion, we will provide step-by-step examples and demonstrate the practicality of these conversions in real-world scenarios.

By the end of this article, readers will have a solid understanding of how to perform infix to prefix conversion in Java, enabling them to handle complex expressions more effectively and efficiently. Whether you are a beginner exploring the intricacies of expression evaluation or an experienced developer seeking optimization techniques, this article will equip you with the necessary knowledge to tackle infix to prefix conversion in Java with confidence.

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 in Java Examples

Here, is the infix to prefix examples:

• Consider the infix expression: (3 + 4 * 2) / (1 – 5)
• Reverse the infix expression: )5 – 1(/ )2 * 4 + 3(
• Convert all opening brackets to closing brackets and vice versa: ( )2 * 4 + 3( )/ 1 – 5(
• The modified infix expression is: )5 – 1(/ )2 * 4 + 3(
• Apply the infix to postfix algorithm on the modified infix expression:
• The postfix expression is: / * 4 + 3 ( – 1 5 ) 2 5
• Reverse the postfix expression to obtain the prefix expression: 5 2 ) ( 3 + 4 * / 1 – 5
• Therefore, the prefix notation of the given infix expression is: 5 2 ) ( 3 + 4 * / 1 – 5

Note: The priority of operators is overridden by brackets, which can also be nested and must be evaluated from inner to outer.

Precedence Order
In descending order => / , * , + , –

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
By mastering infix to prefix conversion in Java, developers can improve the efficiency of their programs, reduce complexity, and enhance the overall performance of expression evaluation. Moreover, this knowledge serves as a valuable foundation for more advanced topics in computer science, such as compiler design and mathematical modeling.
In conclusion, infix to prefix conversion in Java provides a powerful approach to simplify expression evaluation. By understanding the fundamentals and implementing the conversion algorithms, you are equipped to handle a wide range of mathematical expressions effectively. Embrace this knowledge, explore its applications, and continue your journey towards becoming a proficient programmer capable of tackling complex challenges with confidence.

Frequently Asked Questions(FAQs):
Q1: What is the purpose of infix to prefix conversion in Java?
The purpose of infix to prefix conversion in Java is to transform mathematical expressions from the traditional infix notation to the prefix (also known as Polish notation) notation. This conversion allows for easier expression parsing and evaluation in computer programs.

Q2: What are the advantages of using prefix notation over infix notation?
Prefix notation offers several advantages over infix notation, especially in terms of expression evaluation. It eliminates the need for parentheses to indicate the order of operations, making the expressions more concise and less prone to ambiguity. Additionally, prefix notation allows for easy implementation of expression evaluation algorithms using stacks or recursive methods.

Q3.What are some common applications of infix to prefix conversion in Java?
Infix to prefix conversion finds application in a wide range of areas such as mathematical modeling, compiler design, and expression evaluation. It is commonly used in programming languages, calculators, and computer algebra systems to handle complex mathematical expressions efficiently.

Q4: What are the algorithms commonly used for infix to prefix conversion in Java?
There are multiple algorithms available for infix to prefix conversion in Java. Some commonly used ones include the stack-based algorithm using the Shunting Yard algorithm, recursive algorithms based on parsing techniques like the top-down or bottom-up approach, and tree-based algorithms such as expression trees.

Q5: Can infix to prefix conversion handle expressions with variables and functions?
Yes, infix to prefix conversion can handle expressions with variables and functions. The conversion process remains the same, treating variables and functions as operands. However, additional steps might be required to evaluate the expressions involving variables or functions during the evaluation phase.