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