CODEWITHSUNDEEP
javarecursion
Michael Smith
Michael Smith

Reputation: 1867

Java Recursive Math Expression Evaluation

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.

Upvotes: 3

Views: 3561

Answers (2)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

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.

Upvotes: 3

Waylon Flinn
Waylon Flinn

Reputation: 20257

The basic idea here is that pieces of a mathematical expression are just smaller mathematical expressions. You develop a function (or set of functions) that will break an expression down into smaller subexpressions and pass those subexpressions to itself for further processing. You do this until you've broken them all the way down into base elements (in this case, the numbers themselves). At this point you evaluate the base expression and return the result. The value(s) percolate up through the call chain to produce a value for the entire expression at the top of the chain.

Recursion looks something like this:

double getValue(expression){

    if(expression.isBasic)
        return expression.LHS + expression.RHS 
    else
        return getValue(expression.LHS) + getValue(expression.RHS)
}

The twist on your problem is that instead of one function calling itself you'll probably have 4 or 5 that call each other. Which function gets called will depend on what operation you are currently processing in your expression: addition, multiplication, division, etc.

Upvotes: 0

Related Questions