CS2030 Practical Assessment #2

In programming, an expression allows us to combine values and operators together so as to create a new value. The following is an example of an arithmetic expression comprising of the addition + operator (more specifically, binary operator acting on two operands).

2 + 3 + 4

To evaluate an expression, the operator specifies the associativity that dictates the order of operation. Since the addition operator is left-to-right associative, the above expression is evaluated as

2 + 3 + 4 =
5 + 4 =
9

Here is another example involving the addition + and multiplication * (binary) operators.

2 + 3 * 4 + 5

Operators are ordered based on their precedence value such that the lower the precedence value, the higher the precedence. For illustration purposes, suppose the addition operator has precedence value 4 and multiplication has precedence value 3, i.e. multiplication has a higher precedence. The expression is now evaluated as

2 + 3 * 4 + 5 =
2 + 12 + 5 =
14 + 5 =
19

Task

In this task, you are to write a generic expression evaluator that makes use of generic operators. While the sample test cases below makes use of integer arithmetic expressions exclusively, you should bear in mind that the expression evaluation can be performed on expressions of any type. You may also assume that all operators are binary and evaluated with left-to-right associativity.

Take Note!

The following are the constraints imposed on this task. In general, you should keep to the constructs and programming discipline instilled throughout the module.

• Write each class or interface in its own file. Do not use single letter names for classes or interfaces.
• Ensure that ALL object properties and class constants are declared private final, unless otherwise specified.
• Ensure that that your classes are NOT cyclic dependent.
• Do NOT use enumerations, enum.
• ONLY the following java libraries ARE allowed:
  • Comparable, Integer, Object and String from java.lang
  • primitive or generic stream implementations from java.util.stream
  • functional interfaces from java.util.function
  • java.util.Optional
• Use &&, || and ! in logical expressions.
• You are NOT allowed to use java keywords/literals: null, instanceof (except checking for an instance of its own class)
• You are NOT allowed to use the Optional methods: isPresent(), isEmpty(), and get()
• You are NOT allowed to use Java reflection, i.e. Object::getClasses and other methods from Class
• You are NOT allowed to use * wildcard imports.
• You DO NOT need to consider bounded wildcards.
• You are NOT allowed to define anonymous inner classes; define lambdas instead.
• You are NOT allowed to define array constructs, e.g. String[] or using ellipsis, e.g.String...

This task comprises a number of levels. You are required to complete ALL levels.

Level 1

We shall begin by defining the Operator<T> class comprising of the following:

• an of method that takes in a BinaryOperator<T> and a non-zero integer precedence value;
• a toString method that returns the precedence value of the operator as a string;
• an apply method that takes in two arguments of type T and returns the resulting value (of type T) after application of the operator.
• a compareTo method that follows the specifications of the Comparable interface.

jshell> Operator<Integer> add = Operator.<Integer>of((x, y) -> x + y, 4)
add ==> Operator of precedence 4

jshell> add.apply(5, 6)
$.. ==> 11

jshell> Operator<Integer> mul = Operator.<Integer>of((x, y) -> x * y, 3)
mul ==> Operator of precedence 3

jshell> mul.apply(5, 6)
$.. ==> 30

jshell> add instanceof Comparable
$.. ==> true

jshell> List.of(add, mul).stream().
   ...> sorted().
   ...> map(op -> op.apply(5, 6)).
   ...> toList()
$.. ==> [30, 11]

Level 2

Write the Expr<T> class to perform left-to-right expression evaluation with the following methods:

• a method of that takes in a value of type T and initializes the expression with the value;
• a method op that takes in an operator followed by another value, and returns the result of the evaluation after applying the operator;
• a toString method that returns the result of the evaluation as a string enclosed in round brackets.

In this level, you may assume that an expression comprises only one type of operator.

jshell> Expr<Integer> expr = Expr.<Integer>of(2)
expr ==> (2)

jshell> Operator<Integer> add = Operator.<Integer>of((x, y) -> x + y, 4)
add ==> Operator of precedence 4

jshell> Expr.<Integer>of(2).op(add, -3)
$.. ==> (-1)

jshell> expr
expr ==> (2)

jshell> Expr.<Integer>of(2).op(add, -3).op(add, 4).op(add, -5)
$.. ==> (-2)

jshell> Operator<Integer> mul = Operator.<Integer>of((x, y) -> x * y, 3)
mul ==> Operator of precedence 3

jshell> Expr.<Integer>of(2).op(mul, -3).op(mul, 4).op(mul, -5)
$.. ==> (120)

Level 3

Modify the Expr class such that expression evaluation now involves a mix of operators of different precedence.

jshell> Operator<Integer> add = Operator.<Integer>of((x, y) -> x + y, 4)
add ==> Operator of precedence 4

jshell> Operator<Integer> mul = Operator.<Integer>of((x, y) -> x * y, 3)
mul ==> Operator of precedence 3

jshell> Expr.<Integer>of(2).op(mul, 3).op(add, 4) // 2 * 3 + 4
$.. ==> (10)

jshell> Expr.<Integer>of(2).op(add, 3).op(mul, 4) // 2 + 3 * 4
$.. ==> (14)

jshell> Expr.<Integer>of(2).op(add, 3).op(mul, 4).op(mul, 5) // 2 + 3 * 4 * 5
$.. ==> (62)

jshell> Expr.<Integer>of(2).op(add, 3).op(mul, 4).op(add, 5) // 2 + 3 * 4 + 5
$.. ==> (19)

jshell> Expr.<Integer>of(2).op(mul, 3).op(add, 4).op(mul, 5) // 2 * 3 + 4 * 5
$.. ==> (26)

Here's a hint... suppose the current expression is 2 + 3. If the next operator is an addition, say 2 + 3 + 4, then it could be first evaluated to 5 + 4. However, if the next operator is a multiplication, say 2 + 3 * 4, then we cannot evaluate 2 + 3 first; we need to evaluate the expression starting with 3 * 4 (and possibly anything after) to a value, and then perform the addition.

Level 4

Thus far, creating the method pipeline for expression evaluation is rather cumbersome. We would like to simplify the process, but specifically for integer expression evaluation.

You are given the following AbstractIntExpr class:

abstract class AbstractIntExpr extends Expr<Integer> {
    protected static final Operator<Integer> addition = 
        Operator.<Integer>of((x, y) -> x + y, 4);
    protected static final Operator<Integer> multiplication = 
        Operator.<Integer>of((x, y) -> x * y, 3);

    protected AbstractIntExpr(Expr<Integer> expr) {
        super(expr);
    }
}

Write an IntExpr class as a subclass of AbstractIntExpr with the following methods:

• a of method that takes in an integer value and creates an integer expression of the value;
• a add method that takes in an integer value and returns the result after performing integer expression evaluation by adding the value
• a mul method that takes in an integer value and returns the result after performing integer expression evaluation by multiplying the value

jshell> IntExpr.of(2).mul(3).add(4)
$.. ==> (10)

jshell> IntExpr.of(2).add(3).mul(4)
$.. ==> (14)

jshell> IntExpr.of(2).add(3).mul(4).mul(5)
$.. ==> (62)

jshell> IntExpr.of(2).add(3).mul(4).add(5)
$.. ==> (19)

jshell> IntExpr.of(2).mul(3).add(4).mul(5)
$.. ==> (26)

In addition, include appropriate operators and methods to support the following operators:

sub

subtraction, e.g. 3 - 2 = 1 of precedence value 4;

div

integer division, e.g. 3 / 2 = 1 of precedence value 3;

exp

exponentiation (raise to the power of), e.g. 3^2 = 9 of precedence value 2

jshell> IntExpr.of(36).div(6).mul(3).add(2).exp(2).sub(8)
$.. ==> (14)

You should craft other test cases to test out expression evaluation.

Level 5

Lastly, we would like to check that expression evaluation is performed lazily, i.e. only when the result is needed. The following sample run includes a debugging output in the definition of the add and mul operators. Each time an operator is used, a symbol (in this case #) is output. Clearly, the symbols should be output before the value.

jshell> Operator<Integer> add = Operator.<Integer>of((x, y) -> {
   ...>     System.out.println("#");
   ...>     return x + y;
   ...> }, 4)
add ==> Operator of precedence 4

jshell> Operator<Integer> mul = Operator.<Integer>of((x, y) -> {
   ...>     System.out.println("#");
   ...>     return x * y;
   ...> }, 3)
mul ==> Operator of precedence 3

jshell> Expr.<Integer>of(2).op(mul, 3).op(add, 4).op(mul, 5)
#
#
#
$.. ==> (26)

jshell> Expr.<Integer>of(2).op(mul, 3).op(add, 4).op(mul, 5).hashCode() != 0
$.. ==> true

Notice in the last test case that the expression is not evaluated as the result is not necessary; we only require the hash code by calling the hashCode() method of the expression. Hence no symbols are output, i.e. no operation is actually done. This behaviour should also hold when using IntExpr.

In addition, we now allow the following:

jshell> Expr.<Integer>of(2).op(mul, Expr.of(3).op(add, 4)).op(mul, 5)
#
#
#
$.. ==> (70)

jshell> Expr.<Integer>of(2).op(mul, Expr.of(3).op(add, 4)).op(mul, 5).hashCode() != 0
$.. ==> true

Include the overloaded op method in the Expr class that takes in an operator, followed by an expression. This is representative of using brackets to prioritize the evaluation over all other operators. As observed from the sample output, no expression is evaluated until the value is needed.

There is no need to further include additional operation methods in the IntExpr class to take in expressions, as this is a relatively trivial exercise.