Evaluate Tree Expression via Visitor

Question

I have a expression made by composite design pattern:

interface TreeExpression{
    void accept(Visitor visitor);
}

abstract class Operator{
    TreeExpression childA;
    TreeExpression childB;

    Operator(TreeExpression a, TreeExpression b){
        this.childA = a;
        this.childB = b;
    }
}

class PlusTreeExpression extends Operator implements TreeExpression{
    public PlusTreeExpression(TreeExpression a, TreeExpression b) {
        super(a, b);
    }

    public void accept(Visitor visitor) {
        this.childA.accept(visitor);
        visitor.visit(this);
        this.childB.accept(visitor);
    }
}

class MultiplyTreeExpression extends Operator implements TreeExpression{
    public MultiplyTreeExpression(TreeExpression a, TreeExpression b) {
        super(a, b);
    }

    public void accept(Visitor visitor) {
        this.childA.accept(visitor);
        visitor.visit(this);
        this.childB.accept(visitor);
    }
}

class IntegerNode implements TreeExpression{
    Integer value;

    IntegerNode(int v){
        this.value = v;
    }

    public void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

and visitor for getting string from expression:

interface Visitor{
    void visit(PlusTreeExpression tree);
    void visit(MultiplyTreeExpression tree);
    void visit(IntegerNode node);
}

class PrintVisitor implements Visitor{
public StringBuffer result = new StringBuffer();


    public void visit(IntegerNode node) {
        result.append(node.value);
    }

    public void visit(PlusTreeExpression tree) {
        result.append("+");
    }

    public void visit(MultiplyTreeExpression tree) {
        result.append("*");
    }

This visitore works and now I am trying make visitor for evaluate expression but here I have a problem. I tried few ways how to do it but I don't know how to get value from child tree into root without changing existing code.

Answer 1

As far as I can see the problem here is that you are defining how the tree will be traversed in the tree itself and not in the visitor. While this can be a valid approach (design patterns do have variations) I think that in this case is better to decouple the tree structure from the traversing order (pre-order, in-order, post-order). As a matter of fact a typical exercise when teaching this pattern is to write the three visitors, each one performing a different traversal.

In your case I would:

1. Represent the expressions as a tree just like you did, but removing form the accept the traversing parts. In your code the accept would look like:

   public void accept(Visitor visitor)
   {
       visitor.visit(this);
   }
   

2. Define public getters for the childs of your nodes, so that the visitor can access them (getChildA(), getChildB() and getValue()).

3. Write a visitor for the type of traversal that you need. For evaluating the expression you will generally use a post-order while for printing the expression you can use in-order (as in your example). So, for evaluating the expression you will end with something that looks like this:

   class EvalVisitor implements Visitor{
   
           public Integer visit(IntegerNode node) {
               return node.getValue();
           }
   
           public Integer visit(PlusTreeExpression tree) {
               return this.visit(tree.getChildA()) + this.visit(tree.getChildB());
           }
   
           public Integer visit(MultiplyTreeExpression tree) {
               return this.visit(tree.getChildA()) * this.visit(tree.getChildB());
           }
       }
   

HTH