Recursive Descent Parser - Adding Unitialized Variables

Question

So, I have a recursive descent parser that analyzes a mathematical expression in infix. The expression is tokenized, parsed with the aforementioned parser, which generates an AST on the fly (with nodes for each type of expression) and evaluates the final value. I am handling all of these values as doubles; so, I use this parser like so:

Parser parser = new Parser();

try {
    ExpressionNode expression = parser.parse("5 + 4*cos(pi)");
    System.out.println("The value of the expression is "
            + expression.getValue());
} catch (ParserException | EvaluationException e) {
    System.out.println(e.getMessage());
}

}

With Exceptions I defined myself. The line expression.getValue() returns a double, and the way my parser works is that every expression node returns a double, so each branch is evaluated bottom up, until it finally ends up at one double answer.

The thing is, I want to handle unitialized variables in my expressions, like so if I wanted to parse 5 + x (where x is not initialized prior) the expression's value would return 5 + x.

Would I have to change my expression node's getValue() return type to a String? I feel like that would complicate and bloat the program, and there must be a better way to accomplish this. Does anyone have any experience with this type of thing?

I know the description of my parser might have been a little vague, so this is where I learned how to implement most of it.

Answer 1

I assume in your expression tree you have classes defined for operators and constants. You will need to define a new class for variables.

You will then need to add a method like getAllVariables which can return all variables below any point in the tree.

The I suggest you change getValue to accept a Map<String, Double> to provide values for any variables at evaluation time. This will need to be ignored by all nodes other than variables which will return their own value from the map. If they don't find a mapping for themselves as a key they should throw an EvaluationException.

Finally if you want to be able to print out the expression as a string then that's really a separate method to your getValue. Perhaps getExpressionText. Then each class can override this to return a String representing the expression from that point down with the variables just returning the variable name.

So now once you've parsed your expression you can get all variables, prompt the user for values for them, evaluate the expression for given values (catching the exception if any are undefined) and print it out again.

ExpressionNode expression = Parser.parse("x + 5 * y");
System.out.println(expression.getExpressionText());
System.out.println(expression.getAllVariables());
Map<String, Double> variableValues = new TreeMap<>();
variableValues.put("x", 4);
variableValues.put("y", -2);
System.out.println("Evaluates to " + expression.getValue(variableValues));

I would expect your Variable class to end up looking something like:

public class Variable implements ExpressionNode {
    private final String name;

    public double getValue(Map<String, Double> variableValues) {
        if (variableValues.containsKey(name)) {
            return variableValues.get(name);
        } else {
            throw new EvaluationException(name + " is undefined");
        }
    }

    public String getExpressionText() {
        return name;
    }

    public List<String> getAllVariables() {
        return Arrays.asList(name);
    }
}

Another common operation you might want to perform on an expression tree is to simplify it. That essentially means to evaluate to a constant anything that can be evaluated. In my view the best way to do this is to return a new simplified tree rather than changing the current tree. So I recommend adding a new method to ExpressionNode:

public ExpressionNode simplify();

For variables and constants this would just return this. For operators it needs to do something more complicated. Something like:

class Operator implements ExpressionNode {
    public ExpressionNode simplify() {
    if (getAllVariables().isEmpty()) {
        return new Constant(getValue());
    } else {
        Operator simplified = new Operator(operation);
        for (ExpressionNode operand: operands) {
            simplified.addOperand(operand.simplify());
        }
        return simplified;
    }
}

Hopefully you see what that does. If the operation can be completely evaluated then it's converted to a constant. Otherwise it remains an operation but each of its operands is simplified in turn.

So now if you want to simplify an expression you can do:

System.out.println(Parser.parse("7 * 2 + x * 3").simplify().getExpressionText());

Which will return "14 + x * 3".

If you then want to get even more sophisticated you can build awareness of association and distribution into your operators and change simplify so that it reorganises the tree to group variables. But I believe that's a bit beyond the scope of this question!