Convert infix equation to postfix in java

We know stack is first in and last out. The first to go inside a stack is going to be the last to come out of it.

So, the aloglrithm to convert a infix to postfix is simple.

1. We print all the operands. Operands are something which are not mathematical symbols and does not represent any mathematical operation.
2. We push operators into the stack.
   1. If the current operator that we read from the equation or string has lower operator precedence than the current operator on the top of the stack. Then we pop and print the operators until all
      higher precendece operators are popped out or stack becomes empty.
   2. Push the current operator in the stack.
3. Special case for parentheses. If we find the closing parentheses ‘(‘ then we pop and print the elements in the stack until a opening paranthes ‘)’ is popped out.

We are going to have a string of operators.

String operators = "+-*/^";

We are going to have a an array of integers, which contains the precendec of operators.
So, integer at index 0 is precedence of ‘+’ symbol, index at 1 is precedence of ‘-‘ symbol and so on.

int[] operatorPrecedence = {1, 1, 2, 2,3};

I am going to explain the code here.

if (operators.indexOf(ch) < 0 && ch != '(' && ch != ')') {
    System.out.print(ch);
}

In above code, if the current charachter is not an operator or a parentheses, then print the charachter.

If it is an opening parenthese then push it in the stack

else if(ch == '(') {
    stack.push(ch);
}

If the charachter is a closing parentheses then pop the elements from the stack and print it, until the closing parentheses is found.

if(ch == ')') {
    while (!stack.empty()) {
        char bracket = stack.pop();
        if(bracket == '(') break;
            System.out.print(bracket);
        }
}

In the else part we handle the operators.

If the top of the parentheses is an opening parentheses or a lower precedence operator then push the charachter into the stack.

Otherwise, pop the stack and print the elements until a lower precedence operator is at the top of the stack or stack is empty.

Then push the charachter into the stack.

else {
    while (!stack.empty()) {
        char topOperator = stack.peek();
        if (topOperator == '(' ||
         operatorPrecedence[operators.indexOf(ch)] >
           operatorPrecedence[operators.indexOf(topOperator)]) {
               break;
           }
           System.out.print(stack.pop());
          }
   stack.push(ch);
}

Complete Code :-

package datastructures.stack;

import org.jetbrains.annotations.NotNull;

import java.util.Stack;

public class InfixToPostfix {
    String equation_1 = "a+b*c+d";
    String equation_2 = "1*9+4/4";
    String equation_3 = "a+b*(c^d-e)^(f+g*h)-i";
    String operators = "+-*/^";
    int[] operatorPrecedence = {1, 1, 2, 2,3};

    Stack<Character> stack = new Stack<>();

    public static void main(String... args) {
        InfixToPostfix infixToPostfix = new InfixToPostfix();
        infixToPostfix.printPostFix(infixToPostfix.equation_1);
        System.out.printf("%n-------%n");
        infixToPostfix.printPostFix(infixToPostfix.equation_2);
        System.out.printf("%n-------%n");
        infixToPostfix.printPostFix(infixToPostfix.equation_3);

    }

    private void printPostFix(@NotNull String equation) {
        char[] chars = equation.toCharArray();
        for (char ch : chars) {
            if (operators.indexOf(ch) < 0 && ch != '(' && ch != ')') {
                System.out.print(ch);
            } else if(ch == '(') {
                stack.push(ch);
            } else if(ch == ')') {
                    while (!stack.empty()) {
                        char bracket = stack.pop();
                        if(bracket == '(') break;
                        System.out.print(bracket);
                    }
            } else {
                while (!stack.empty()) {
                    char topOperator = stack.peek();
                    if (topOperator == '(' ||
                            operatorPrecedence[operators.indexOf(ch)] >
                            operatorPrecedence[operators.indexOf(topOperator)]) {
                        break;
                    }
                    System.out.print(stack.pop());
                }
                stack.push(ch);
            }
        }
        while (!stack.empty()) System.out.print(stack.pop());
    }
}