Infix to Postfix Java

The infix and postfix expressions can have the following operators: ‘+’, ‘-‘, ‘%’,’*’, ‘/’ and alphabets from a to z. The precedence of the operators (+, -) is lesser than the precedence of operators (*, /, %). Parenthesis has the highest precedence and the expression inside it must be converted first. In this section, we will learn how to convert infix expression to postfix expression and postfix to infix expression through a Java program.

For performing the conversion, we use Stack data structure. The stack is used to store the operators and parenthesis to enforce the precedence Start parsing the expression from left to right. Before moving ahead in this section, ensure that you are friendly with the stack and its operations. Let’s have a look at infix and postfix expressions.

Infix Expression

Infix expressions are those expressions in which the operator is written in-between the two or more operands. Usually, we use infix expression. For example, consider the following expression.

Postfix Expression

Postfix expressions are those expressions in which the operator is written after their operands. For example, consider the following expression.

Infix vs Postfix Expression

Infix Expression	Postfix Expression
A*B/C	AB*C/
(A/(B-C+D))(E-A)C	ABC-D+/EA-C
A/B-C+DE-AC	AB/C-DEAC-

Infix to Postfix Conversion Example

Convert the (X – Y / (Z + U) * V) infix expression into postfix expression.

S.N.	Input	Operand Stack	Postfix Expression
1	(	(	–
2	X	(	X
3	–	( –	X
4	Y	( –	XY
5	/	( – /	XY
6	(	( – / (	XY
7	Z	( – / (	XYZ
8	+	( – / ( +	XYZ
9	U	( – / ( +	XYZU
10	)	( – /	XYZU+
11	*	( – *	XYZU+/
12	V	( – *	XYZU+/V
13	)	–	XYZU+/V*-

Algorithm

Scan the infix notation from left to right one character at a time.
If the next symbol scanned as an operand, append it to the postfix string.
If the next symbol scanned as an operator, the:
1. Pop and append to the postfix string every operator on the stack that:
  1. Is above the most recently scanned left parenthesis, and
  2. Has precedence higher than or is a right-associative operator of equal precedence to that of the new operator symbol.
2. Push the new operator onto the stack
If a left parenthesis is scanned, push it into the stack.
If a right parenthesis is scanned, all operators down to the most recently scanned left parenthesis must be popped and appended to the postfix string. Furthermore, the pair of parentheses must be discarded.
When the infix string is fully scanned, the stack may still contain some operators. All the remaining operators should be popped and appended to the postfix string.

Let’s implement the above algorithm in a Java program.

Java Program to Convert Infix Expression into Postfix Expression

InfixToPostfixConversion.java

  import java.io.*;  class Stack  {  char a[]=new char[100];  int top=-1;  void push(char c)  {  try  {  a[++top]= c;  }  catch(StringIndexOutOfBoundsException e)  {  System.out.println(“Stack full, no room to push, size=100”);  System.exit(0);  }  }  char pop()  {  return a[top–];  }  boolean isEmpty()  {  return (top==-1)?true:false;  }  char peek()  {  return a[top];  }  }  public class InfixToPostfix  {  static Stack operators = new Stack();  public static void main(String argv[]) throws IOException  {  String infix;  //create an input stream object  BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));  //get input from user  System.out.print(“nEnter the infix expression you want to convert: “);  infix = keyboard.readLine();  //output as postfix  System.out.println(“Postfix expression for the given infix expression is:” + toPostfix(infix));  }  private static String toPostfix(String infix)  //converts an infix expression to postfix  {  char symbol;  String postfix = “”;  for(int i=0;i();++i)>

Output:

Infix to Postfix Java

Postfix to Infix Conversion Example

Convert the AB + CD – / postfix expression into infix expression.

S.N.	Input	Operand Stack	Infix Expression
1	A	A	–
2	B	A, B	–
3	+	A + B	A+ B
4	C	A + B, C	–
5	D	A + B, C, D	–
6	–	A + B, C – D	C – D
7	/	A + B / C – D	A + B / C – D

Algorithm

Read the postfix expression from left to right one character at a time.
If it is operand push into operand stack.
If it is an operator, then:
1. Pop two operand from the stack.
2. From infix expression and push into the operand stack
If the expression is not ended go to the first step.
Pop operand stack and display.
Exit

Let’s implement the above algorithm in a Java program.

Java Program to Convert Postfix Expression into Infix Expression

PostfixToInfixConversion.java

  import java.util.Scanner;  import java.util.Stack;  public class PostfixToInfixConversion  {  //user-defined function that checks the character is operator or not      private boolean isOperator(char ch)   {  if (ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ || ch == ‘^’)  //returns true if either of the operator is found  return true;  //else returns false  return false;  }  //user-defined function that performs conversion  public String convertPostfixToInfix(String postfixstring)   {  //implementing stack      Stack<String> s = new Stack<>();  //iterates over the postfix expression  for (int i = 0; i < postfixstring.length(); i++)   {  //reading a character at a time      char ch = postfixstring.charAt(i);  //inside the if-statement we have called the user-defined function that checks whether the character is operator or not  if (isOperator(ch))   {  String b = s.pop();  String a = s.pop();  //push the character (operator) into stack in between the string a and b  s.push(“(” + a + ch + b + “)”);  }   else  //push character into the stack  s.push(“” + ch);  }  //pop character from the stack and returns the same  return s.pop();  }  public static void main(String args[])   {  //creating object of the class  PostfixToInfixConversion obj = new PostfixToInfixConversion();  Scanner sc = new Scanner(System.in);  System.out.print(“Enter the postfix expression you want to convert: “);  //reads a postfix expression from the user  String postfixstring = sc.next(); //for example ab+  //prints the infix expression  System.out.println(“Infix expression for the given postfix expression is: ” + obj.convertPostfixToInfix(postfixstring));  }  }  

Output:

Infix to Postfix Java

Next TopicMemory Leak in Java

Infix to Postfix Java

Infix to Postfix Java

Infix Expression

Postfix Expression

Infix vs Postfix Expression

Infix to Postfix Conversion Example

Algorithm

Java Program to Convert Infix Expression into Postfix Expression

Postfix to Infix Conversion Example

Algorithm

Java Program to Convert Postfix Expression into Infix Expression

How to Update Java

Java Big Data Frameworks

You may also like