Evaluate Post Fix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a post fix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Tokenize the expression depending on the delemeter.
2. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 2 and second one being operand 1.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
3. Pop the stack for the result.

Time Complexity : O(N)

Algorithm Execution:

Input Expression : 1 2 3 * +

Step 1 : Stack[1]

Step 3 : Stack[1, 2]

Step 4 : Stack[1,2,3]

Step 5 : Stack[1,6]

Step 5 : Stack[7] - Result

	public String evalPostFix(String input, String delemeter){
	Stack<String> stack = new Stack<String>(input.length());
	StringBuffer sf = null;
	StringTokenizer st = new StringTokenizer(input, delemeter);
	String token = null;
	String operand1, operand2;
	while (st.hasMoreTokens()) {
	token = st.nextToken();
	if(isOperand(token)){
	stack.push(token);
	}else{
	sf = new StringBuffer();
	operand2 = stack.pop();
	operand1 = stack.pop();
	sf.append(operand1);
	sf.append(token);
	sf.append(operand2);
	stack.push(evaluateExpression(sf.toString())+"");
	}
	}
	return stack.pop();
	}

view raw java hosted with ❤ by GitHub

You can fork the source code and unit tests from github.