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