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

In other words, this expression is computing the product of two sums. Here is the
same expression written in the more familiar infix notation:

(2.6 + 3.7) * (5.2 + 18.7)

These expressions can become arbitrarily complex. The key observation to make
about them is that they all begin with an operator. In other words, every prefix
expression is of one of two forms:

• A simple number

• An operator followed by two operands

This observation will become a roadmap for our recursive solution. The sim-
plest prefix expression will be a number, and we can distinguish it from the other
case because any other expression will begin with an operator. So we can begin
our recursive solution by checking whether the next token in the Scanner is a
number. If it is, we have a simple case and we can simply read and return the
number:

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
...

}

}

Turning our attention to the recursive case, we know that the input must be an
operator followed by two operands. We can begin by reading the operator:

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();
...

}

}