Symbolic library design pattern

Question

I am building a java library for symbolic calculations. I have made an abstract expression class that I use to do various operations between products, fractions and polynomials. However, things got complicated when I wanted to add floors and ceiling. As I am aware that there are such libraries around I'd like to know if there is a specific design pattern to follow or if there is any resource I can look into for inspiration and guidance.

Answer 1

Most probably what you are doing is parsing a "context-free language" (Type-2 according to the Chomsky hierarchy). Try reading http://en.wikipedia.org/wiki/LL_parser and http://en.wikipedia.org/wiki/Pushdown_automaton - you don't necessarily have to understand the math behind but it will give you the clue.

And I agree with you that the Composite design patter is very useful for the object representation of the expression. The following example comes from my code which purpose was to hold and print an expression, but you may easily modify it to catch the idea.

Expression is the root object. It has descendants such as CompoundExpression, Number, Variable etc.

public interface Expression {
    /**
     * @return a numeric value of the expression
     */
    double getValue();

    /**
     * @return a string representation of the expression
     */
    String getExpression();

    /**
     * @return true if the expression is an atomic expression
     */
    boolean isLeaf();
}

CompoundExpression is the container for an operation as its operands.

public class CompoundExpression implements Expression {

    /**
     * Creates a compound expression.
     * @param operation the specified operation
     * @param operands The specified operands. The amount of operands must exactly
     * match the arity of the operation.
     */
    public CompoundExpression(Operation operation, Expression ... operands) {
        super();
        this.operands = Arrays.asList(operands);
        this.operation = operation;
    }

    /**
     * The expressions which this expression is compound of ;)
     */
    final private List<Expression> operands;

    /**
     * The operation on operands.
     */
    final private Operation operation;

    /**
     * {@inheritDoc}
     */
    @Override
    public String getExpression() {
        return this.operation.compose(this.operands);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public double getValue() {
        return this.operation.calculate(this.operands);
    }

    /** 
     * {@inheritDoc}
     */
    @Override
    public int hashCode() {
        ....
    }

    /** 
     * {@inheritDoc}
     */
    @Override
    public boolean equals(Object obj) {
        ....
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isLeaf() {
        return false;
    }
}

Number is a leaf. You may implement more types of leafs, such as Variable.

public class Number implements Expression {

    /**
     * Creates an atomic expression with the specified value.
     * @param value the numeric value
     */
    public Number(double value) {
        super();
        this.value = value;
    }

    /**
     * The numeric value of the number.
     */
    private double value;

    /**
     * {@inheritDoc}
     */
    @Override
    public String getExpression() {
        return String.valueOf(this.value);
    }

    /** 
     * {@inheritDoc}
     */
    @Override
    public double getValue() {
        return this.value;
    }

    /** 
     * {@inheritDoc}
     */
    @Override
    public int hashCode() {
        ....
    }

    /** 
     * {@inheritDoc}
     */
    @Override
    public boolean equals(Object obj) {
        ....
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isLeaf() {
        return true;
    }
}

Operation holds the operation, such as Plus, Sinus, Floor, Ceiling, ... It may also have the ability to actually calculate the value if required.

public interface Operation {

    /**
     * Returns a numeric value of the operation performed on the given operands.
     * 
     * @param operands the list of operands
     * @return a numeric value of the operation
     */
    double calculate(List<Expression> operands);

    /**
     * Returns a string representation of the operation performed on the given operands.
     * @param operands operands the list of operands
     * @return a string representation of the operation
     */
    String compose(List<Expression> operands);

    /**
     * Returns a string representation of the operator
     * @return string representation of the operator
     */
    String getOperator();
}

BinaryOperation is a parent of all the binary operations. Its not necessarily needed, but having it is convenient.

public abstract class BinaryOperation implements Operation {

    /**
     * {@inheritDoc}
     */
    @Override
    public String compose(List<Expression> operands) {
        assert (operands.size() == 2);

        final Expression op1 = operands.get(0);
        final Expression op2 = operands.get(1);
        final boolean op1Leaf = op1.isLeaf();
        final boolean op2Leaf = op2.isLeaf();
        final StringBuilder builder = new StringBuilder();
        if (!op1Leaf) {
            builder.append("(");
        }
        builder.append(op1.getExpression());
        if (!op1Leaf) {
            builder.append(")");
        }
        builder.append(this.getOperator());
        if (!op2Leaf) {
            builder.append("(");
        }
        builder.append(op2.getExpression());
        if (!op2Leaf) {
            builder.append(")");
        }
        return builder.toString();
    }
}

An example of a binary operation:

public class PlusOperation extends BinaryOperation {

    /**
     * {@inheritDoc}
     */
    @Override
    public double calculate(List<Expression> operands) {
        assert (operands.size() == 2);
        return operands.get(0).getValue() + operands.get(1).getValue();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String getOperator() {
        return "+";
    }

}    

UnaryOperation is a parent of all the unary operations. Its not necessarily needed, but having it is convenient.

public abstract class UnaryOperation implements Operation {

    /**
     * {@inheritDoc}
     */
    @Override
    public String compose(List<Expression> operands) {
        assert (operands.size() == 1);
        return this.getOperator() + "(" + operands.get(0).getExpression() + ")";
    }

}

An example of an unary operation:

public class CosinusOperation extends UnaryOperation {

    /**
     * {@inheritDoc}
     */
    @Override
    public double calculate(List<Expression> operands) {
        assert (operands.size() == 1);
        return Math.cos(operands.get(0).getValue());
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String getOperator() {
        return "cos";
    }
}

How to use all of it. You may "manually" create an expression like this:

Expression exp = new CompoundExpression(
    new PlusOperation(),
    new CompoundExpression(
        new DivisionOperation(),
        new CompoundExpression(
            new PlusOperation(), 
            new Number(2), 
            new Number(3)
        ),
        new Number(4)
    ), 
);

And you have to create the expression by using an implementation of a push-down automaton :)