java - 通过访问者评估树表达式

Question

我有一个复合设计模式的表达：

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);
    }
}

和访问者从表达式中获取字符串：

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("*");
    }

这个访问者有效，现在我正在尝试让访问者进行评估表达式，但在这里我遇到了问题。我尝试了几种方法来做到这一点，但我不知道如何在不更改现有代码的情况下从子树中获取价值。

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

Answer 2

情侣提示：

1. 对于您的问题：考虑一种称为“堆栈”的数据结构（在 Javajava.util.LinkedList中很有帮助），并研究一种称为“反向波兰表示法”的东西。

2. 顺便说一句，您可能希望简化您的方法。请注意，此代码一遍又一遍地重复：

   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).