Java Program to Convert Infix Expression to Postfix expression
In this article let us discuss how to convert an infix expression to a postfix expression using Java.
Pre-Requisites:
1. Infix expression: Infix expressions are expressions where an operator is in between two operators. It is the generic way to represent an expression or relationship between the operators and operands mathematically. Example: 3 * 5, a + b
2. Postfix expression: Postfix expressions are expressions where an operator is placed after all of its operands. Example: 3 5 *, a b +
3. Required Data structures:
Stack: Stack is a linear data structure that follows the Last-In-First-Out principle. we are going to use a Stack data structure for the conversion of infix expression to postfix expression. To know more about the Stack data structure refer to this article β Stack Data Structure.
Rules to Convert Infix Expression to Postfix Expression
There are certain rules used for converting infix expressions to postfix expressions as mentioned below:
- Initialize an empty stack to push and pop the operators based on the following rules.
- You are given an expression string to traverse from left to right and while traversing when you encounter an
- operator: you can directly add it to the output (Initialize a data structure like a list or an array to print the output which stores and represents the required postfix expression).
- operand: pop the operands from the stack and add them to the output until the top of the stack has lower precedence and associativity than the current operand.
- open-parenthesis ( β ( β ): push it into the stack.
- closed-parenthesis ( β ) β ): Pop the stack and add it to the output until open-parenthesis is encountered and discard both open and closed parenthesis from the output.
- Once you traverse the entire string, pop the stack and add it to the output, until the stack is empty.
Operators |
Precedence |
Associativity |
---|---|---|
^ |
Highest |
Right to Left |
*, / |
High |
Left to Right |
+, β |
Low |
Left to Right |
To know more about Precedence and Associativity, refer to this article β Precedence β Associativity
Example Explaining the Conversion
Letβs consider an example to demonstrate the conversion of infix expression to postfix expression using stack.
Infix expression: 3 * 5 + ( 7 β 3 )
Procedure:
Step |
Character Element |
Stack |
Output (Postfix Expression) |
The Operation Performed on the Stack |
---|---|---|---|---|
1. |
3 |
3 |
β |
|
2. |
* |
* |
3 |
push β*β |
3. |
5 |
* |
3 5 |
β |
4. |
+ |
* + |
3 5 * |
pop β*β push β+β |
5. |
( |
+ ( |
3 5 * |
push β(β |
6. |
7 |
+ ( |
3 5 * 7 |
β |
7. |
β |
+ ( β |
3 5 * 7 |
push β-β |
8. |
) |
3 5 * 7 β + |
pop β-β pop β+β |
The output of the Infix expression 3 * 5 + ( 7 β 3 ) is 3 5 * 7 β +
Implementation:
Input: 3 * 5 + ( 7 β 3 )
Output: 3 5 * 7 β +
Letβs implement the above procedure using Java:
Java
// Java Program to Convert Infix // expression to Postfix expression import java.util.*; // Driver Class public class InfixPostfixConversion { // lets define a method for conversion of infix // expression to postfix expression public static String infixToPostfix(String infix) { // The output will be represented as postfix StringBuilder postfix = new StringBuilder(); // Initialize the stack to // store the operators Stack<Character> stk = new Stack<>(); for ( char c : infix.toCharArray()) { // if the encountered character is an operand // add it to the output i.e postfix if (Character.isLetterOrDigit(c)) { postfix.append(c); // if the encountered character is '(' push // it to the stack(stk) } else if (c == '(' ) { stk.push(c); // if the encountered character is ')' pop // the stack(stk) until '(' is encountered } else if (c == ')' ) { while (!stk.isEmpty() && stk.peek() != '(' ) { postfix.append(stk.pop()); } stk.pop(); // discard '(' by popping it from // the stack } else { // if the encountered character is not // parenthesis or operand, then check the // precendence of the operator and pop the // stack and add it to the output // until the top of the stack has lower // precedence than the current character while (!stk.isEmpty() && precedence(stk.peek()) >= precedence(c)) { postfix.append(stk.pop()); } stk.push(c); // push the current operator to // the stack } } // After traversing the entire string, check whether // the stack is empty or not, if the stack is not // empty, pop the stack and add it to the output*/ while (!stk.isEmpty()) { postfix.append(stk.pop()); } return postfix.toString(); } // define a method to check the precedence of the // operator public static int precedence( char operator) { switch (operator) { case '+' : case '-' : return 1 ; case '*' : case '/' : return 2 ; default : return 0 ; } } // main function public static void main(String[] args) { System.out.println( "Enter a Infix expression:" ); Scanner sc = new Scanner(System.in); String infix = sc.next(); sc.close(); String postfix = infixToPostfix(infix); System.out.println( "Postfix Expression: \n" + postfix); } } |
Output:
Enter a Infix expression: 3*5+(7-3)
Postfix Expression: 35*73-+
Complexity of the Above Method:
Time complexity: O(n) to traverse the entire string at least once.
Space complexity: O(n) for using stack space.