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 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.