Infix to Prefix Conversion in Java

February 8, 2021

Infix to Prefix Conversion:-

In this page we will learn the infix to prefix conversion in Java .

Suppose there are two operands A and B and an operator (op) , the infix conversion implies that op will be placed in between a and b i.e a op b. When the operator is placed after both operands i.e ab op , it is called postfix notation. And when the operator is placed before the operands i.e op ab , the expression in prefix notation.

let us see how to do this in java :-

ALGORITHM:

Reverse the given infix expression.
Do Infix to postfix conversion and get the result.
Reverse the result to get the final expression. (prefix expression) .

Java code :

import java.util.Stack;
public class InfixToPreFix {
    static int precedence(char c){
        switch (c){
            case ‘+’:
            case ‘-‘:
                return 1;
            case ‘*’:
            case ‘/’:
                return 2;
            case ‘^’:
                return 3;
        }
        return –1;
    }

    static StringBuilder infixToPreFix(String expression){

        StringBuilder result = new StringBuilder();
        StringBuilder input = new StringBuilder(expression);
        input.reverse();
        Stack<Character> stack = new Stack<Character>();

        char [] charsExp = new String(input).toCharArray();
        for (int i = 0; i < charsExp.length; i++) {

            if (charsExp[i] == ‘(‘) {
                charsExp[i] = ‘)’;
                i++;
            }
            else if (charsExp[i] == ‘)’) {
                charsExp[i] = ‘(‘;
                i++;
            }
        }
        for (int i = 0; i <charsExp.length ; i++) {
            char c = charsExp[i];

            if(precedence(c)>0){
                while(stack.isEmpty()==false && precedence(stack.peek())>=precedence(c)){
                    result.append(stack.pop());
                }
                stack.push(c);
            }else if(c==‘)’){
                char x = stack.pop();
                while(x!=‘(‘){
                    result.append(x);
                    x = stack.pop();
                }
            }else if(c==‘(‘){
                stack.push(c);
            }else{
                //character is neither operator nor “(“
                result.append(c);
            }
        }

        for (int i = 0; i <=stack.size() ; i++) {
            result.append(stack.pop());
        }
        return result.reverse();
    }

    public static void main(String[] args) {
        String exp = “A+B*(C^D-E)”;
        System.out.println(“Infix Expression: “ + exp);
        System.out.println(“Prefix Expression: “ + infixToPreFix(exp));
    }
}

Output:

Infix Expression: A+B*(C^D-E)
Prefix Expression: +A*B-^CDE