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:

Post a Comment