Оценка дерева выражений с помощью Visitor

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

Это visitore работ и теперь я пытаюсь сделать посетитель для оценки выражения, но здесь у меня проблема. Я пробовал несколько способов, как это сделать, но я не знаю, как получить значение из дочернего дерева в корневой каталог без изменения существующего кода.

Answer 1

Насколько я вижу, проблема в том, что вы определяете, как дерево будет проходить в самом дереве, а не в посетителе. Хотя это может быть допустимым подходом (шаблоны проектирования имеют вариации), я думаю, что в этом случае лучше отделить древовидную структуру от порядка перемещения (предварительный заказ, порядок, пост-порядок). На самом деле типичное упражнение при обучении этой схеме состоит в том, чтобы написать трех посетителей, каждый из которых выполняет другой обход.

В вашем случае я бы:

1. Представляет выражения в виде дерева так же, как вы делали, но устранил из акцепта проникающих частей. В вашем коде акцепта будет выглядеть так:

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

2. Определить общественные добытчик для Чайлдса ваших узлов, так что посетитель может получить доступ к ним (getChildA(), getChildB() и getValue()).

3. Напишите посетителю, что вам нужно. Для оценки выражения вы обычно используете post-order while для печати выражения, которое вы можете использовать в порядке (как в вашем примере). Таким образом, для вычисления выражения вы закончите с чем-то, что выглядит следующим образом:

   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. На ваш вопрос: рассмотреть структуру данных, называемую "стек" (в Java, java.util.LinkedList полезно), и посмотреть на то, что называется "Reverse Polish Notation".

2. Кстати, вы можете упростить свой подход. Обратите внимание на то, что этот код повторяется снова и снова:

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

Вот только собирается получить хуже, как вы добавите больше случаев. Вы можете рассмотреть возможность создания абстрактного класса, называемого (скажем) BinaryExpression, содержащего часть или весь этот код.

Возможно, вы также можете использовать какой-либо целочисленный токен, чтобы идентифицировать конкретную операцию, а не имя класса и функцию accept() ... а затем использовать оператор switch/case в вашем «посетителе» "для visit(BinaryExpression).