Java Program To Convert Infix Expression To Postfix (Stack)

In this article, we will learn how we can convert Infix expressions to Postfix using the Java programming language.

I have also included the variable description and the algorithm for this program later in this article.

Logic Explanation

This program works on the basis of the following logic:

• Each and every character is extracted from the inputted String using a for-loop.
• If the character is a letter or digit(variable, e.g. A, B, C, etc. Or number like 1, 2, 3, etc.), it is directly printed on the screen.
• If the character is an opening first bracket ( ‘(‘ ), it is directly pushed into the Stack.
• If the character is a closing first bracket ( ‘)’ ), every element contained inside this and the previous opening first bracket, are popped out of the Stack and printed on the screen.
• If the character is an operator (^, *, /, +, -), it is handled according to its priority. If its priority is higher than the operator before it, it is pushed into the stack otherwise, the operators before it that are higher or equal in priority, are popped out and are printed on the screen, until an ‘(‘ appears. Then, this operator is pushed into the stack.
• After the for-loop runs through the whole length of the expression, the remaining elements in the Stack are printed on the screen.

Java Code

PLEASE NOTE THAT I HAVE USED HashMap FOR STORING THE PRIORITY OF THE OPERATOR. IF YOU ARE UNFAMILIAR WITH HashMap, PLEASE USE ANY OTHER DATA STRUCTURE LIKE AN array OR ArrayList, WHICHEVER YOU’RE FAMILIAR WITH. ALSO, I HAVE USED BufferedReader FOR TAKING INPUT FROM THE USER. YOU MAY USE Scanner FOR THE SAME.

import java.io.*;
import java.util.*;

class TechRBun_Infix_Postfix {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String exp; //store the expression.
        char sym; //to extract each character of the expression.
        Stack<Character> st=new Stack<>(); //stack
        HashMap<Character,Integer> priority=new HashMap<>(); //store the priority of the operators
        priority.put('^',3); //priority of the '^' operator is set 3.
        //priority of '*' and '/' are same and are set to 2. 
        priority.put('*',2);
        priority.put('/',2);
        //priority of '+' and '-' are same and are set to 1.
        priority.put('+',1);
        priority.put('-',1);
        System.out.println("ENTER AN INFIX EXPRESSION");
        exp=br.readLine();
        for(int i=0;i<exp.length();i++){
            sym=exp.charAt(i);
            if(sym=='(')
                st.push(sym);
            else{
                if(Character.isLetterOrDigit(sym))
                    System.out.print(sym);
                else{
                    if(sym==')'){
                        while(st.peek()!='(')
                            System.out.print(st.pop());
                        st.pop();
                    }
                    else{
                            while(st.size()>0 && st.peek()!='(' && priority.get(sym)<=priority.get(st.peek()))
                            System.out.print(st.pop());
                            st.push(sym);
                    }
                }
            }
        }
//printing the remaining elements in the Stack
        while (st.size()>0)
            System.out.print(st.pop());
    }
}

DRY RUN

Let’s see this algorithm in action with an example.

Here’s an Infix expression: (A+B)-C*D/(E-F/G). Let’s calculate its postfix version using the above algorithm.

S.NO.	SYMBOL	STACK	PRINT
1	(	PUSH (
2	A		A
3	+	PUSH +
4	B		B
5	)	PUSH ) AND POP + FROM 3	+
6	–	PUSH –
7	C		C
8	*	PUSH *
9	D		D
10	/	PUSH / AND POP * FROM 8 (AS PRIORITY OF / AND *A RE SAME.	*
11	(	PUSH (
12	E		E
13	–	PUSH –
14	F		F
15	/	PUSH /
16	G		G
17	)	PUSH ) AND POP / FROM 15 AND – FROM 13	/-
		AT LAST, THE REMAINING ELEMENTS FROM THE STACK, THAT IS, / FROM 10 AND – FROM 6 GETS POPPED.	/-

Thus, the final output is: AB+CD*EFG/-/-, which is the required output.

We can also cross-check this as follows:-

(A+B)-C*D/(E-F/G)
=AB+ – C*D/(E-FG/)
=AB+ -C*D/(EFG/-)
=AB+ -CD* / EFG/-
=AB+ -CD*EFG/-/
=AB+CD*EFG/-/-

WHICH IS THE REQUIRED OUTPUT.

VARIABLE DESCRIPTION

VARIABLE NAME	DATA TYPE	PURPOSE
exp	String	To store the given expression.
sym	char	To extract and store each element of the expression.
priority	HashMap	To store the priority of each operator (^, *, /, +, -).
st	Stack	To form the Stack of the operators.

Algorithm

1. START.
2. INCLUDING THE java.io PACKAGE.
3. INCLUDING THE java.util PACKAGE.
4. DECLARING CLASS TechRBun_Infix_Postfix.
5. DECLARING THE main METHOD.
6. DECLARING AN OBJECT br OF THE BufferedReader class WITH (new InputStreamReader(System.in)) AS ITS PARAMETER.
7. DELCARING A String variable exp.
8. DECLARING A char VARIABLE sym.
9. CREATING AN OBJECT st FOR Stack.
10. CREATING AN OBJECT priority FOR HashMap.
11. SET THE PRIORITY OF ^ TO 3.
12. SET THE PRIORITY OF * TO 2.
13. SET THE PRIORITY OF / TO 2.
14. SET THE PRIORITY OF + TO 1.
15. SET THE PRIORITY OF – TO 1.
16. DISPLAY “ENTER AN INFIX EXPRESSION”
17. STORE THE USER’S INPUT IN exp.
18. REPEAT FOR I=0 TO exp.length().
    17.1. SET SYM=exp.charAt(i).
    17.2. CHECK IF (sym=='(‘) THEN PUSH sym INTO THE STACK ELSE
    17.2.1. CHECK IF (sym is a letter) THEN DISPLAY sym ELSE
    17.2.1.1. CHECK IF (sym==’)’) THEN
    17.2.1.1.1. REPEAT while(st.peek()!='(‘)
    17.2.1.1.1.1. DISPLAY (st.pop()).
    17.2.1.1.2. END OF WHILE LOOP.
    17.2.1.1.3. st.pop().
    17.2.1.2. END OF ELSE.
    17.2.1.3. ELSE
    17.2.1.3.1. REPEAT WHILE (st.size()>0 AND st.peek()!='(‘ AND priority.get(sym)<=priority.get(st.peek()))
    17.2.1.3.1.1. DISPLAY (st.pop()).
    17.2.1.3.1.2. CLOSING OF WHILE LOOP.
    17.2.1.3.2. st.push(sym).
19. CLOSING OF ALL THE OPEN ELSE BLOCKS.
20. REPEAT UNTIL STACK IS EMPTY.
    19.1. DISPLAY (st.pop()).
21. CLOSING OF LOOP.
22. CLOSING OF main METHOD.
23. CLOSING OF THE CLASS.
24. STOP.

If you have any doubts regarding this program, feel free to comment down below and I will surely help you out.

Kindly share this article with your friends if you have found it helpful.

Have a great day ahead!