
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 | |
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
- START.
- INCLUDING THE java.io PACKAGE.
- INCLUDING THE java.util PACKAGE.
- DECLARING CLASS TechRBun_Infix_Postfix.
- DECLARING THE main METHOD.
- DECLARING AN OBJECT br OF THE BufferedReader class WITH (new InputStreamReader(System.in)) AS ITS PARAMETER.
- DELCARING A String variable exp.
- DECLARING A char VARIABLE sym.
- CREATING AN OBJECT st FOR Stack.
- CREATING AN OBJECT priority FOR HashMap.
- SET THE PRIORITY OF ^ TO 3.
- SET THE PRIORITY OF * TO 2.
- SET THE PRIORITY OF / TO 2.
- SET THE PRIORITY OF + TO 1.
- SET THE PRIORITY OF – TO 1.
- DISPLAY “ENTER AN INFIX EXPRESSION”
- STORE THE USER’S INPUT IN exp.
- 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). - CLOSING OF ALL THE OPEN ELSE BLOCKS.
- REPEAT UNTIL STACK IS EMPTY.
19.1. DISPLAY (st.pop()). - CLOSING OF LOOP.
- CLOSING OF main METHOD.
- CLOSING OF THE CLASS.
- 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!
Wow that was unusual. I just wrote an very long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say great blog!