Evaluate PreFix 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 prefix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Reverse the expression.
2. Tokenize the expression depending on the delemeter.
3. 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 1 and second one being operand 2.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
4. Pop the stack for the result.

Time Complexity : O(N^2)

Difference against the Post Fix Evaluation :

1. We have to reverse in the first instance.
2. In prefix evaluation we have to treat the first pop as operand 1 and second pop as operand 2 unlike post fix evaluation

Algorithm Execution:

Input Expression : + 1 * 2 3

Step 1 : + 1 * 2 3 => 3 2 * 1 +

Step 2 : Stack[3]

Step 3 : Stack[3, 2]

Step 4 : Stack[6]

Step 5 : Stack[6,1]

Step 5 : Stack[7] - Result

Time Complexity : O(N)

	public String evalPreFix(String input, String delemeter){
	Stack<String> stack = new Stack<String>(input.length());
	StringBuffer sf = new StringBuffer(input);
	input = sf.reverse().toString();
	StringTokenizer st = new StringTokenizer(input, delemeter);
	String token = null;
	while (st.hasMoreTokens()) {
	token = st.nextToken();
	if(isOperand(token)){
	stack.push(token);
	}else{
	sf = new StringBuffer();
	sf.append(stack.pop());
	sf.append(token);
	sf.append(stack.pop());
	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.