Wednesday, May 8, 2013

Postfix expression evaluation

Algorithm:
for each expression token:
if the token is a number:
push it
else (the token is an operator, OP):
second = pop();
first = pop();
compute: result = first OP second
push the result on the stack

when there are no more tokens, pop the answer off the stack
4 2 3 - -

token stack
----- -----
[]
4 [4]
2 [2, 4]
3 [3, 2, 4]
- [-1, 4]
- [5]
END [] ⇒ answer = 5

public static Double evaluatePostfix(String rpn) {
char[] exp = rpn.toCharArray();
Stack<Double> stack = new Stack<Double>();

int len = exp.length;
for (int i = 0; i < len; i++) {
if (!isOperator(exp[i])) {
stack.push(Double.parseDouble("" + exp[i]));
} else {
double b = stack.pop();
double a = stack.pop();
stack.push(evaluate(a, b, exp[i]));
}
}
double result = stack.pop();
System.out.println("Result:" + result);
return result;
}

private static Double evaluate(double a, double b, char operator) {
double result = 0.0;
switch (operator) {
case '/':
result = a / b;
break;
case '*':
result = a * b;
break;
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
}
return result;
}
 

No comments: