CODEWITHSUNDEEP
javaoopdesign-patternsvisitor-pattern
Marek Čačko
Marek Čačko

Reputation: 1010

Evaluate Tree Expression via Visitor

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.

Upvotes: 5

Views: 6507

Answers (2)

Andrés Fortier
Andrés Fortier

Reputation: 1693

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

Upvotes: 9

Tim
Tim

Reputation: 1675

Couple hints:

  1. To your question: consider a data structure called a "stack" (in Java, java.util.LinkedList is helpful), and look into something called "Reverse Polish Notation".

  2. Incidentally, you might want to simplify your approach. Notice that this code is repeated over and over:

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

That's only going to get worse as you add more cases. You might want to consider creating an abstract class called (say) BinaryExpression, containing some or all of that code.

You might also consider using some kind of integer token to identify the specific operation, rather than the name of the class and and "accept()" function ... and then using a switch/case statement in your "Visitor" implementation for visit(BinaryExpression).

Upvotes: 0

Related Questions