Recursion - Building Java Programs: A Back to Basics Approach - page 757

At this point we reach a critical decision. We have read in the operator, and now
we need to read in the first operand and then the second operand. If we knew that the
operands were simple numbers, we could write code like the following:
// not the right approach
public static double evaluate(Scanner input) {
if (input.hasNextDouble()) {
// base case with a simple number
return input.nextDouble();
} else {
// recursive case with an operator and two operands
String operator = input.next();
double operand1 = input.nextDouble();
double operand2 = input.nextDouble();
...
}
}
But we have no guarantee that the operands are simple numbers. They might be
complex expressions that begin with operators. Your instinct might be to test
whether or not the original operator is followed by another operator (in other
words, whether the first operand begins with an operator), but that reasoning
won't lead you to a satisfactory outcome. Remember that the expressions can be
arbitrarily complex, so either of the operands might contain dozens of operators to
be processed.
The solution to this puzzle involves recursion. We need to read two operands from
the Scanner , and they might be very complex. But we know that they are in prefix
form and we know that they aren't as complex as the original expression we were
asked to evaluate. The key is to recursively evaluate each of the two operands:
public static double evaluate(Scanner input) {
if (input.hasNextDouble()) {
// base case with a simple number
return input.nextDouble();
} else {
// recursive case with an operator and two operands
String operator = input.next();
double operand1 = evaluate(input);
double operand2 = evaluate(input);
...
}
}
This simple solution works. Of course, we still have the task of evaluating the
operator. After the two recursive calls have executed, we will have an operator and