Conversion from infix to postfix/prefix expression

The conversion from infix notation to prefix notation involves reversing the order of the expression, replacing each operator with its corresponding prefix operator, and swapping the positions of each operand.

• The final result is a prefix expression with the operator appearing before the operands.

Here’s an overview of how you can implement the conversion algorithm:

Conversion from Infix to Postfix:

1. Initialize an empty stack to hold operators.
2. Initialize an empty string to store the postfix expression.
3. Iterate through each character in the infix expression:
   • If the character is an operand (a digit or letter), add it to the postfix string.
   • If the character is an opening parenthesis ‘(‘, push it onto the stack.
   • If the character is a closing parenthesis ‘)’, pop operators from the stack and append them to the postfix string until an opening parenthesis is encountered. Discard the opening parenthesis.
   • If the character is an operator (+, -, *, /, etc.):
     • Pop operators from the stack and append them to the postfix string if they have higher or equal precedence compared to the current operator.
     • Push the current operator onto the stack.
4. After processing all characters, pop any remaining operators from the stack and append them to the postfix string.
5. The resulting string is the postfix expression.

Conversion from Infix to Prefix:

The conversion algorithm for prefix is similar to postfix, but the order of operators and operands is reversed.

To convert infix to prefix:

1. Reverse the infix expression.
2. Convert the reversed infix expression to postfix using the algorithm described above.
3. Reverse the resulting postfix expression to obtain the prefix expression.

Here’s a Java implementation of the conversion from infix to postfix:

import java.util.*;

public class InfixToPostfix {
    public static String infixToPostfix(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        // Define operator precedence
        Map<Character, Integer> precedence = new HashMap<>();
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
        precedence.put('^', 3);

        for (char c : infix.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                postfix.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                }
                stack.pop(); // Discard the '('
            } else { // Operator
                while (!stack.isEmpty() && precedence.getOrDefault(c, 0) <= precedence.getOrDefault(stack.peek(), 0)) {
                    postfix.append(stack.pop());
                }
                stack.push(c);
            }
        }

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

        return postfix.toString();
    }

    public static void main(String[] args) {
        String infixExpression = "a + b * (c - d) / e";
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("Infix Expression: " + infixExpression);
        System.out.println("Postfix Expression: " + postfixExpression);
    }
}