Infix to Postfix Conversion in Java

Infix to Postfix:

Postfix and prefix expressions are used by compilers to do faster calculations as they support operator precedence in order. An Infix expression is what we humans write mathematical logics as.

Understand what Postfix & Infix is

  • Infix Expression: When an operator is in between the two operands
    • Example: A * B is known as infix expression.
  • Postfix Expression: When operator is after the two operands
    • Example: BD * is known as postfix expression.

Algorithm for Infix to Postfix 

  1. Scan infix expression from left to right.
  2.  If there is a character as operand, output it.
  3.  if not
    1. If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
    2. Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5.  If the character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Repeat steps 2-6 until infix expression is scanned.
  7.  display the output
  8. Pop and output from the stack until it is not empty.

Java code :

This method uses internal stack in Java to work with Infix to Postfix
Run
import java.util.Stack;

class Main{
    static boolean checkIfOperand(char ch)
    {
        return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
    }

    // Function to compare precedence
    // If we return larger value means higher precedence
    static int precedence(char ch)
    {
        switch (ch)
        {
            case '+':
            case '-':
                return 1;

            case '*':
            case '/':
                return 2;

            case '^':
                return 3;
        }
        return -1;
    }


    static void covertInfixToPostfix(String expr)
    {
        int i;
        Stack  s = new Stack<>();
        StringBuilder result = new StringBuilder(new String(""));

        for (i = 0; i < expr.length(); ++i)
        {
            // Here we are checking is the character we scanned is operand or not
            // and this adding to output.
            if (checkIfOperand(expr.charAt(i)))
                result.append(expr.charAt(i));

                // Here, if we scan the character ‘(‘, we need to push it to the stack.
            else if (expr.charAt(i) == '(')
                s.push(expr.charAt(i));

                // Here, if we scan character is an ‘)’, we need to pop and print from the stack
                // do this until an ‘(‘ is encountered in the stack.
            else if (expr.charAt(i) == ')')
            {
                while (!s.empty() && s.peek() != '('){
                    result.append(s.peek());
                    s.pop();
                }
                if (!s.empty() && s.peek() != '(')
                    return; // invalid expression
                else
                    s.pop();
            }
            else // if an operator
            {
                while (!s.empty() && precedence(expr.charAt(i)) <= precedence(s.peek())){
                    result.append(s.peek());
                    s.pop();
                }
                s.push(expr.charAt(i));
            }

        }

        // Once all initial expression characters are traversed
        // adding all left elements from stack to exp
        while (!s.empty()){
            result.append(s.peek());
            s.pop();
        }
        System.out.println(result);

    }


    // Driver code
    public static void main(String[] args)
    {
        String expression = "((a+(b*c))-d)";
        covertInfixToPostfix(expression);
    }
}

OUTPUT:

abc*+d-

All Different variation

For the above implementation we had assumed that expression will only have alphabets as operands and ‘(‘ or ‘)’ as braces.

We will also need to take care of the following

  • Operands can be anything alphabets or digits
    • Example – a-z or A-Z or 0 – 9
  • Brackets can be of different variations { } or [ ] or ( )
This method uses internal inbuilt stack implementation in Java
Run
import java.util.Stack;

class LearnCoding{
    static boolean checkIfOperand(char ch)
    {
        return Character.isLetterOrDigit(ch);
    }

    // Function to compare precedence
    // If we return larger value means higher precedence
    static int precedence(char ch)
    {
        switch (ch)
        {
            case '+':
            case '-':
                return 1;

            case '*':
            case '/':
                return 2;

            case '^':
                return 3;
        }
        return -1;
    }


    static void covertInfixToPostfix(String expr)
    {
        int i;
        Stack  s = new Stack<>();
        StringBuilder result = new StringBuilder(new String(""));

        for (i = 0; i < expr.length(); ++i)
        {
            // Here we are checking is the character we scanned is operand or not
            // and this adding to output.
            if (checkIfOperand(expr.charAt(i)))
                result.append(expr.charAt(i));

                // Here, if we scan the character ‘(‘, '[', '{' we need to push it to the stack.
            else if (expr.charAt(i) == '(' || expr.charAt(i) == '[' || expr.charAt(i) == '{')
                s.push(expr.charAt(i));

                // Here, if we scan character is an ‘)’, we need to pop and print from the stack
                // do this until an ‘(‘ is encountered in the stack.
            else if (expr.charAt(i) == ')' || expr.charAt(i) == ']' || expr.charAt(i) == '}')
            {
                if(expr.charAt(i) == ')'){
                    while (!s.empty() && s.peek() != '('){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }

                if(expr.charAt(i) == ']'){
                    while (!s.isEmpty() && s.peek() != '['){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }
                if(expr.charAt(i) == '}'){
                    while (!s.isEmpty() && s.peek() != '{'){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }
            }
            else // if an operator
            {
                while (!s.isEmpty() && precedence(expr.charAt(i)) <= precedence(s.peek())){
                    result.append(s.peek());
                    s.pop();
                }
                s.push(expr.charAt(i));
            }

        }

        // Once all initial expression characters are traversed
        // adding all left elements from stack to exp
        while (!s.isEmpty()){
            result.append(s.peek());
            s.pop();
        }
        System.out.println(result);

    }


    // Driver code
    public static void main(String[] args)
    {
        String expression = "{[x(8+1)]-y}";
        covertInfixToPostfix(expression);
    }
}

This method again uses custom class implementation of stack.
Run
class myStack {
    static final int MAX = 10;
    int top;
    char[] a = new char[MAX]; // Maximum size of Stack

    myStack()
    {
        top = -1;
    }

    boolean push(char x)
    {
        if (top >= (MAX - 1)) {
            System.out.println("Stack Overflow");
            return false;
        }
        else {
            a[++top] = x;
            return true;
        }
    }

    int pop()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return Integer.MIN_VALUE;
        }
        else {
            int x = a[top--];
            return x;
        }
    }

    char peek()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }
        else {
            char x = a[top];
            return x;
        }
    }
    int size(){
        return (top+1);
    }

    boolean isEmpty(){
        return top==-1;
    }

    boolean isFull(){
        return top == MAX - 1;
    }
}

class Main{
    static boolean checkIfOperand(char ch)
    {
        return Character.isLetterOrDigit(ch);
    }

    // Function to compare precedence
    // If we return larger value means higher precedence
    static int precedence(char ch)
    {
        switch (ch)
        {
            case '+':
            case '-':
                return 1;

            case '*':
            case '/':
                return 2;

            case '^':
                return 3;
        }
        return -1;
    }


    static void covertInfixToPostfix(String expr)
    {
        int i;
        myStack s = new myStack();
        StringBuilder result = new StringBuilder(new String(""));

        for (i = 0; i < expr.length(); ++i)
        {
            // Here we are checking is the character we scanned is operand or not
            // and this adding to output.
            if (checkIfOperand(expr.charAt(i)))
                result.append(expr.charAt(i));

                // Here, if we scan the character ‘(‘, '[', '{' we need to push it to the stack.
            else if (expr.charAt(i) == '(' || expr.charAt(i) == '[' || expr.charAt(i) == '{')
                s.push(expr.charAt(i));

                // Here, if we scan character is an ‘)’, we need to pop and print from the stack
                // do this until an ‘(‘ is encountered in the stack.
            else if (expr.charAt(i) == ')' || expr.charAt(i) == ']' || expr.charAt(i) == '}')
            {
                if(expr.charAt(i) == ')'){
                    while (!s.isEmpty() && s.peek() != '('){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }

                if(expr.charAt(i) == ']'){
                    while (!s.isEmpty() && s.peek() != '['){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }
                if(expr.charAt(i) == '}'){
                    while (!s.isEmpty() && s.peek() != '{'){
                        result.append(s.peek());
                        s.pop();
                    }

                    s.pop();
                }
            }
            else // if an operator
            {
                while (!s.isEmpty() && precedence(expr.charAt(i)) <= precedence(s.peek())){
                    result.append(s.peek());
                    s.pop();
                }
                s.push(expr.charAt(i));
            }

        }

        // Once all initial expression characters are traversed
        // adding all left elements from stack to exp
        while (!s.isEmpty()){
            result.append(s.peek());
            s.pop();
        }
        System.out.println(result);

    }


    // Driver code
    public static void main(String[] args)
    {
        String expression = "{[x(8+1)]-y}";
        covertInfixToPostfix(expression);
    }
}

Output

x81+y-

ADVANTAGE OF POSTFIX:

  1. Any formula can be expressed without parenthesis.
  2. It is very convenient for evaluating formulas on computer with stacks.
  3. Postfix expression doesn’t has the operator precedence.
  4. Postfix is slightly easier to evaluate.
  5. It reflects the order in which operations are performed.
  6. You need to worry about the left and right associativity.