Java Recursive Math Expression Evaluation

Question

I have a problem assigned for school that really has me confused. Basically, in class we are learning about recursion. As homework, and an introduction to mutual recursion, we are supposed to write a math expression evaluator that uses mutual recursion. The three methods, getExpressionValue, getTermValue, and getFactorValue need to call each other in order to get the result. We are supposed to support addition, subtraction, multiplication, division, and parenthesized expressions. In searching for ideas on how to do this, I keep coming across recursive descent parsing, but I am not sure if that idea is appropriate for this problem.

If someone could provide me with guidance or maybe a link to an article that explains how to do parsing like this, I would be very appreciative. Thanks.

Answer 1

Recursive descent parsing is indeed appropriate for this. The Wikipedia article on the subject contains a nice example in C which is quite similar to what you want to do.

The basic idea is this: If you assume that the text you've been given is a valid expression, it must start with either a left parenthesis or with a number. So by looking at the first character, you know whether it is a parentheseized expression or not. If it is not, the text must be a sequence of one or more terms separated by + or -. So then you start treating the start of the text as a term. What is a term? It is a sequence of one or more factors separated by * or /. So you start treating the start of the text as a factor. What is a factor? It is either a number or a parenthesized expression, and by looking that the first character, you can determine what it is. If it is a digit, you consume all subsequent digits so that you find out what the number is. Now, the method that tried to figure out what the factor value was can return this number to the method that tries to figure out what the term value is. This method now knows what the first number is, and it can check the next character to see if it is a * or a / (edit: it could also be a right parenthesis, a + or a -, which would mean that this term consisted of only one number), then ask for the next factor to be extracted, and so on.