Infix to Postfix

Infix to Postfix Conversion using Stack in JAVA

In this program, you'll learn to solve the Infix to Postfix Conversion using Stack. There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Example : 

• infix (1+2)*(3+4)

• with parentheses: ((1+2)*(3+4))

• in postfix: 12+34+*

• in prefix: *+12+34

• infix 1^2*3-4+5/6/(7+8)

• paren.: ((((1^2)*3)-4)+((5/6)/(7+8)))

• in postfix: 12^3*4-56/78+/+

• in prefix: +-*^1234//56+78

Algorithm

1. Scan the Infix string from left to right.
2. Initialise an empty stack.
3. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character tostack.
4. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack). If topStack has higher precedence over the scanned character Popthe stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
5. (After all characters are scanned, we have to add any character that the stackmay have to the Postfix string.) If stack is not empty add topStack to Postfix stringand Pop the stack. Repeat this step as long as stack is not empty.
6. Return the Postfix string.

Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+.
The algorithm for the conversion is as follows :
Repeat this step till all the characters are scanned.

	import java.util.Scanner;
	public class Infix2Postfix extends Stack {
	public Infix2Postfix(int x) {
	super(x);
	}
	/**
	* @return postfixString value
	*/
	public String InToPost(String infixString) {
	String postfixString = "";
	for (int index = 0; index < infixString.length(); ++index) {
	char chValue = infixString.charAt(index);
	if (chValue == '(') {
	push('(');
	} else if (chValue == ')') {
	Character oper = (Character) peek();
	while (!(oper.equals('(')) && !(isEmpty())) {
	postfixString += oper.charValue();
	oper = (Character) peek();
	pop();
	}
	} else if (chValue == '+' || chValue == '-') {
	//Stack is empty
	if (isEmpty()) {
	push(chValue);
	//current Stack is not empty
	} else {
	Character oper = (Character) peek();
	while (!(isEmpty() || oper.equals(new Character('(')) || oper.equals(new Character(')')))) {
	pop();
	postfixString += oper.charValue();
	}
	push(chValue);
	}
	} else if (chValue == '*' || chValue == '/') {
	if (isEmpty()) {
	push(chValue);
	} else {
	Character oper = (Character) peek();
	while (!oper.equals(new Character('+')) && !oper.equals(new Character('-')) && !isEmpty()) {
	pop();
	postfixString += oper.charValue();
	}
	push(chValue);
	}
	} else {
	postfixString += chValue;
	}
	}
	while (!isEmpty()) {
	Character oper = (Character) peek();
	if (!oper.equals(new Character('('))) {
	pop();
	postfixString += oper.charValue();
	}
	}
	return postfixString;
	}
	public static void main(String[] args) {
	Infix2Postfix mystack = new Infix2Postfix(10);
	System.out.println("Type in an expression like (1+2)*(3+4)/(12-5)\n "
	+ "with no monadic operators like in-5 or +5 followed by key");
	Scanner scan = new Scanner(System.in);
	String str = scan.next();
	System.out.println("The Expression you have typed in infix form :\n" + str);
	System.out.println("The Equivalent Postfix Expression is :\n" + mystack.InToPost(str));
	}
	}

view raw

When you run the program, the output will be:

Type in an expression like (1+2)*(3+4)/(12-5)
 with no monadic operators like in-5 or +5 followed by key
(1+2)*(3+4)
The Expression you have typed in infix form :
(1+2)*(3+4)
The Equivalent Postfix Expression is :
12+34++*