CC-9 : Convert Infix expression to Postfix expression.

Description:

Given an Infix expression, convert it to a Postfix expression.

Test cases and expected outputs:

Input Parameters	Expected outputs
Infix: K+L-MN+(O^P)W/U/V*T+Q	PostFix: KL+MN-OP^WU/V/T*+Q+
Infix: A-B-DE/F+BC	PostFix: AB-DEF/-BC+

Pseudocode:

getPrecedence() method

Returns the mathematical precedence of operator characters.

Precedence of :

+ , - is 1.

* , / is 2.

^ is 3.

infixtoPostfix() method

Initialize a stack for processing purposes.

Initialize a StringBuilder named postFix to hold the result of processing.

For each character in input infix string:

If current character is not an operator or a bracket append it to postFix.

If current character is a starting bracket, add it to the stack.

If current character is an ending bracket:

While current character is not a starting bracket:

Add current character to postFix.

Remove current character from stack.

Else:

Call getPrecedence() for current character.

While precedence of current character is less that precedence of character at top of stack:

Remove character from top of stack and add it to postFix.

Add current character to stack.

While stack is not empty:

Remove top character fromstack and add it to postFix.

Return postFix.

Code:

public class StackInfixToPostfix {
	
private Deque<Character> stack=null;	

private int getPrecedence(char c) {
	int pre=0;
	switch (c) {
	case '+':
		pre=1;
		break;
	case '-':
		pre=1;
		break;
	case '*':
		pre=2;
		break;
	case '/':
		pre=2;
		break;
	case '^':
		pre=3;
		break;	
	default:
		pre=-1;
		break;
	}
	return pre;	
}

public String infixToPostfix(String str) throws Exception{
	stack=new LinkedList<Character>();	
	StringBuilder postFix=new StringBuilder();
	char[] chr=str.toCharArray();
	String operator="+-*/^"; 	String brackets="()";
	char c, tempC; int prec, tempCPrec;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if ((operator.indexOf(c)==-1)&&(brackets.indexOf(c)==-1)) {
			postFix.append(c);
		}else if (c=='(') {
			stack.offerFirst(c);
		}else if (c==')') {
			while ((stack.size()!=0)&&(stack.peekFirst()!='(')) {
				    postFix.append(stack.pollFirst());
			    }	
			stack.pollFirst();
		} else {
			prec=getPrecedence(c);
			while (stack.size()!=0) {
				tempC=stack.peekFirst();
				tempCPrec=getPrecedence(tempC);
				if (prec <= tempCPrec) {
					postFix.append(stack.pollFirst());					
				}else {
					break;
				}
			}
			stack.offerFirst(c);
		}
		
	}
	while (stack.size()!=0) {
		postFix.append(stack.pollFirst());
	}
	return postFix.toString();
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.LinkedList;

public class StackInfixToPostfix {
	
private Deque<Character> stack=null;	

private int getPrecedence(char c) {
	int pre=0;
	switch (c) {
	case '+':
		pre=1;
		break;
	case '-':
		pre=1;
		break;
	case '*':
		pre=2;
		break;
	case '/':
		pre=2;
		break;
	case '^':
		pre=3;
		break;	
	default:
		pre=-1;
		break;
	}
	return pre;	
}

public String infixToPostfix(String str) throws Exception{
	stack=new LinkedList<Character>();	
	StringBuilder postFix=new StringBuilder();
	char[] chr=str.toCharArray();
	String operator="+-*/^"; 	String brackets="()";
	char c, tempC; int prec, tempCPrec;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if ((operator.indexOf(c)==-1)&&(brackets.indexOf(c)==-1)) {
			postFix.append(c);
		}else if (c=='(') {
			stack.offerFirst(c);
		}else if (c==')') {
			while ((stack.size()!=0)&&(stack.peekFirst()!='(')) {
				    postFix.append(stack.pollFirst());
			    }	
			stack.pollFirst();
		} else {
			prec=getPrecedence(c);
			while (stack.size()!=0) {
				tempC=stack.peekFirst();
				tempCPrec=getPrecedence(tempC);
				if (prec <= tempCPrec) {
					postFix.append(stack.pollFirst());					
				}else {
					break;
				}
			}
			stack.offerFirst(c);
		}
		
	}
	while (stack.size()!=0) {
		postFix.append(stack.pollFirst());
	}
	return postFix.toString();
}
			

 	
public static void main(String[] args) {
	/************************
	 Test Cases given below:
	 ************************/
	try {
	StackInfixToPostfix convert=new StackInfixToPostfix();
	String retVal;
	System.out.println("\n\nInfix: "+"K+L-M*N+(O^P)*W/U/V*T+Q");
	retVal=convert.infixToPostfix("K+L-M*N+(O^P)*W/U/V*T+Q");
	System.out.print("PostFix: "+ retVal);
	
	System.out.println("\n\nInfix: "+"A-B-D*E/F+B*C");
	retVal=convert.infixToPostfix("A-B-D*E/F+B*C");
	System.out.print("PostFix: "+ retVal);
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
	}
	
}

Input Parameters	Expected outputs
Infix: K+L-MN+(O^P)W/U/V*T+Q	PostFix: KL+MN-OP^WU/V/T*+Q+
Infix: A-B-DE/F+BC	PostFix: AB-DEF/-BC+