0

I need to design a program in Java which calculates arithmetic expressions (only addition or subtraction).

Requirements:

1) abstract class Expression which contains abstract method calculate() and method equals() which overrides Object.

2) concrete class AtomicExpression which inherits from Expression and must have a constructor which receives a real number. This class represents a single number.

3) abstract class CompoundExpression which inherits from Expression and has a constructor which receives 2 Expression objects (two operands). This class represents an arithmetic expression with 2 operands.

4) concrete classesAdditionExpression and SubtractionExpression whose constructors also receive 2 Expression objects. These classes actually calculate the expressions with 2 operands.

My natural instinct was to add a result instance field and constructor to Expression which would store the result of an expression. If it's atomic expression then the result would be the number itself. If we're dealing with a compound expression then we'll store the result of the expression in result. But then CompoundExpression also inherits from Expression as well as receives 2 Expression objects in its own constructor. So CompoundExpression can't really initialize its parent (Expression has one field, CompoundExpression receives two parameters).

If I were to forgo a constructor in Expression then I can't really override equals in Expression because I need to be able to make comparison based on some field.

How can I solve this conundrum?

  • 4
    Please just follow the requirements exactly. There is no need for fields other than those that are required to persist the arguments passed to the constructors. There is especially no result since the Expression type is supposed to calculate its result only when calling calculate(). – poke Nov 14 '17 at 14:59
  • ok so how can I override equals from Expression? what will my equals compare? – Yos Nov 14 '17 at 15:01
  • 1
    When is expr1 equal to expr2? This is maths: e.g. 4 + 2 is equal to 3 + 3. So two expressions are apparently equal when their calculation results in the same result? – poke Nov 14 '17 at 15:03
  • 1
    AdditionExpression will just receive two Expression objects, yes. The point of the compound expressions is that they can take any kind of expression. So doing something like 2 + ((3 + 4) + (7 - 2)) is easily possible (it would be Add(Atomic(2), Add(Add(Atomic(3), Atomic(4)), Subtract(Atomic(7), Atomic(2))))) – poke Nov 14 '17 at 15:13
  • 1
    @Yos: Is there a reason to assume that the default equals implementation is insufficient here? By default, equals will consider every Expression object as distinct from all others. – Bart van Ingen Schenau Nov 14 '17 at 15:21
3

You're working with what we might call an Abstract Syntax Tree.

The purpose of the tree is to capture an expression. There are other ways to capture expressions, such as text. A text form is a serialization. In some serializations of expressions (e.g. infix), we need to use parenthesis — ()'s — to override operator precedence; however, in an AST, the operator precedence is explicit in the shape of the tree, so no parenthesis are necessary.

We capture expressions as trees for a variety of reasons. In compiler technology, expressions are often represented as trees at some point in the translation process (e.g. parse output). The compiler's task is to translate the expression into a form (usually lower level, like byte-code or machine code) for later execution (or further translation for later execution).

Such a tree might also be evaluated instead of translated; this might occur, for example, in an interpreter. In an interpreter, usually evaluation of such an expression tree would happen after the construction of the tree; this is because the interpreter may choose to analyze the expression (tree) before evaluation, and/or, because the interpreter wants to be able to evaluate the expression more than once — each time with possibly different values for variables, so the same expression can yield a different final result if variables are updated.

In your case as there are no variables (only constants), there is no (obvious) advantage to delaying execution — so you might be tempted to consider doing execution as part of construction. This would imply having a result or value for all entities before construction, and so you might provide, in the abstract base class, a constructor that receives the value, and a field that holds the value; however, as you note, that would require that the CompoundExpression and AdditionExpression also construct in terms of values, and this would be a different assignment.

By the text of your requirements, (1) you must provide a calculate() method for (post-construction) evaluation of the expression, and (2) you must provide a constructor for AdditionExpression that takes two Expressions and no values!!

Your job is to support tree construction for later evaluation, not to build a tree while simultaneously computing its final value. So, separate those concepts in your mind — construction of the tree from evaluation of the tree. Evaluation will be done post construction.

If I were to forgo a constructor in Expression then I can't really override equals in Expression because I need to be able to make comparison based on some field.

To repeat myself, you are conflating construction with evaluation. In the model of those requirements, construction happens first, and evaluation is delayed until construction is completed.

The override for equals(...) will execute only in the post-construction environment. No one will call equals during construction of the tree, eh?

Thus, in your equals override you can assume that trees are fully constructed! Fully constructed trees support the interface provided by the abstract class Expression — they can be evaluated to obtain their value!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.