Last time we took a procedural approach to solve the expression problem.
This time I will demonstrate an object-oriented approach. As a
reminder, we want to model the following forms of expressions,
| number |
Literal |
| expr + expr |
Add |
| expr - expr |
Subtract |
| expr * expr |
Multiply |
| expr / expr |
Divide |
The most natural thing to do in an object-oriented language is to make each of the above
expression forms its own class. First, I will introduce a base class to provide an expression abstraction.
abstract class Expr {
}
Now I will now create a sub-class for each expression.
class Literal: Expr {
protected double Value;
public Literal(double value) {
Value = value;
}
}
abstract class BinaryExpr: Expr {
protected Expr Left;
protected Expr Right;
public BinaryExpr(Expr left, Expr right) {
Left = left;
Right = right;
}
}
class Add: BinaryExpr {
public Add(Expr left, Expr right) : base(left, right) { }
}
class Subtract: BinaryExpr {
public Subtract(Expr left, Expr right) : base(left, right) { }
}
class Multiply: BinaryExpr {
public Multiply(Expr left, Expr right) : base(left, right) { }
}
class Divide: BinaryExpr {
public Divide(Expr left, Expr right) : base(left, right) { }
}
I created a base class for the binary expressions which I will take
advantage of below.
To evaluate the expression I will add an abstract virtual method,
Evaluate(), to Expr.
abstract class Expr {
public abstract double Evaluate();
}
Then I will override the Evaluate() method for
each of the above classes. Evaluating a literal is simply returning the value of
the literal so I modified the Literal class to,
class Literal: Expr {
protected double Value;
public Literal(double value) {
Value = value;
}
public override double Evaluate() {
return Value;
}
}
All binary expressions need to evaluate their left-hand expression and
right-hand expression and then perform their operation on the results. To represent this, I
overrode Evaluate() to evaluate both Left and Right
and then call a newly introduced EvaluateOp()
method. I sealed the Evaluate() method because I want
descendants to override EvaluateOp() not
Evaluate().
abstract class BinaryExpr: Expr {
protected Expr Left;
protected Expr Right;
public BinaryExpr(Expr left, Expr right) {
Left = left;
Right = right;
}
public sealed override double Evaluate() {
return EvaluateOp(Left.Evaluate(), Right.Evaluate());
}
protected abstract double EvaluateOp(double left, double right);
}
Now I can implemented the concrete descendents of BinaryExpr.
class Add: BinaryExpr {
public Add(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left + right;
}
}
class Subtract: BinaryExpr {
public Subtract(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left - right;
}
}
class Multiply: BinaryExpr {
public Multiply(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left * right;
}
}
class Divide: BinaryExpr {
public Divide(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left / right;
}
}
The advantages an object-oriented approach are,
- New data types can be added without affecting any of the other data
types.
- Each data type is encapsulated, only the data type needs to have access
the instance variables.
- All the operations affecting the instance variables are in one place,
the methods of instance variable's class.
- New operations can be added as abstract methods. The compiler will then
generate an error if an operation is not implemented for one of the leaf
classes.
- Efficient storage is natural. Adding field to one of the expression
types do not affect the others.
To demonstrate how easy it is to add a new data type I will again add support
for Power.
To do this I will add a class to represent the Power expression form.
This looks like,
class Power: BinaryExpr {
public Power(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return Math.Pow(left, right);
}
}
Note that the Power data type can be added without
modifying the other classes.
The disadvantages to an object-oriented approach are,
- It is difficult to add new operations because adding an operation
requires modifying all the classes.
- The logic for each operation is spread over multiple classes and often
multiple files. This makes it cumbersome to get a complete picture what the
operation does.
- It is very difficult to dynamically add operations and can't be done
without careful planning.
To demonstrate some of the difficulties of adding a new operation, I will add
the Print operation. First I will modify the base Expr
class to add an abstract Print() method.
abstract class Expr {
public abstract double Evaluate();
public abstract void Print();
}
Now I will override this method in each class similar to the way I did for
the Evaluate() method.
class Literal: Expr {
protected double Value;
public Literal(double value) {
Value = value;
}
public override double Evaluate() {
return Value;
}
public override void Print() {
Console.Write(Value);
}
}
abstract class BinaryExpr: Expr {
protected Expr Left;
protected Expr Right;
public BinaryExpr(Expr left, Expr right) {
Left = left;
Right = right;
}
public sealed override double Evaluate() {
return EvaluateOp(Left.Evaluate(), Right.Evaluate());
}
protected abstract double EvaluateOp(double left, double right);
public sealed override void Print() {
Left.Print();
PrintOp();
Right.Print();
}
protected abstract void PrintOp();
}
class Add: BinaryExpr {
public Add(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left + right;
}
protected override void PrintOp() {
Console.Write(" + ");
}
}
class Subtract: BinaryExpr {
public Subtract(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left - right;
}
protected override void PrintOp() {
Console.Write(" - ");
}
}
class Multiply: BinaryExpr {
public Multiply(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left * right;
}
protected override void PrintOp() {
Console.Write(" * ");
}
}
class Divide: BinaryExpr {
public Divide(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return left / right;
}
protected override void PrintOp() {
Console.Write(" / ");
}
}
class Power: BinaryExpr {
public Power(Expr left, Expr right) : base(left, right) { }
protected override double EvaluateOp(double left, double right) {
return Math.Pow(left, right);
}
protected override void PrintOp() {
Console.Write(" ^ ");
}
}
As you can see, each of the classes needed to be modified to implement
Print(). You can also note that the compiler
complained until each of the classes implemented the Print()
operation. This is because we used an abstract method in the
Expr class.
If you compare the procedural approach vs. the object-oriented approach you
will notice that they are pretty much opposites. It is easy to add operations in
the procedural approach but difficult using an object-oriented approach. Adding
data types is difficult using in a procedural approach, but easy in an
object-oriented approach. Data needs to be public in procedural, but can be
private in object oriented. When deciding which approach to use you need to try
an predict what will occur more often, adding new data types or adding new
operations. What I will present next are some compromise solutions that balance
the advantages and disadvantages.