Как оценивать выражения в этом дереве?

Question

Вот пример разбираемого файла XML Я работаю с этой вкладкой его в виде дерева

commandList 

    assign 
    variable 
     #text[a] 
    expression-int 
     #text[1] 

    assign 
    variable 
     #text[b] 
    expression-int 
     #text[2] 

    assign 
    variable 
     #text[c] 
    expression-operation 
     operator 
     #text[OP_SET] 
     arguments 
     expression-variable 
      variable 
      #text[a] 
     expression-variable 
      variable 
      #text[b] 

    assign 
    variable 
     #text[d] 
    expression-operation 
     operator 
     #text[OP_SET] 
     arguments 
     expression-operation 
      operator 
      #text[OP_TUPLE] 
      arguments 
      expression-int 
       #text[1] 
      expression-int 
       #text[2] 
     expression-operation 
      operator 
      #text[OP_TUPLE] 
      arguments 
      expression-int 
       #text[3] 
      expression-int 
       #text[4] 

Я надеюсь, что этот вход не трудно понять. Вот как это выглядит нормально, когда не разобрано из файла XML:

a := 1; 
b := 2; 
c := {1,2}; 
d := {(1,2),(3,4)}; 

и т.д ...

Всех пар назначения (то есть, значение и переменный) должен храниться в hashmap, так что значение может быть просмотрено его переменной и использовано в последующих выражениях. Я должен использовать рекурсивный оценщик спуска (я думаю?), Чтобы разрешить выражения в соответствии с грамматикой.

В течение последних 24 часов я искал всевозможные вещи и видел множество оценщиков деревьев для базовой арифметики (например, 2 + 3 * 8 и т. Д.), Но не смог увидеть, как это будет работайте для моего конкретного дерева.

Код, который я написал до сих пор, находится так же быстро, как поиск имен переменных (a, b, c, d, e и т. Д.), Но я не могу придумать, как закодировать рекурсию, которая обеспечит правильные значения для хэш-карты.

public void evaluate(Node node){ 
    HashMap<String, String> assignments = new HashMap<String, String>(); 
    NodeList assignment = node.getChildNodes(); 
    for (int i=0; i < assignment.getLength(); i++){ //1 to 13 
     Node assign = assignment.item(i); 
     Node variable = this.getChild(assign, 0); 
     Node varValNode = this.getChild(variable, 0); 
     String varVal = varValNode.getNodeValue(); 

     Node expression = this.getChild(assign, 1); 

Документ, узел и Nodelist классы для моего дерева необычны тем, что они не позволяют метод «GetChild», который я думаю, что позволит сэкономить много времени. Кто-нибудь знает, почему это?

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

EDIT: Кроме того, второй «ввод», который я поставил выше, был фактически выходом. Это должно было быть так:

a := 1; 
b := 2; 
c := @set(a,b); 
d := @set(@tuple(1,2),@tuple(3,4)); 

Answer 1

Предполагая, что все значения целого типа, то необходимо создать HashMap<string,Integer> для хранения значений переменных, и передать его в evaluate метод:

public static void main(String[] args) { 
    NodeList commandList = ... // get your XML from somewhere 
    Map<string,Integer> vars = new HashMap<string,Integer>(); 
    for (Node node : commandList) { 
     evaluate(node, vars); 
    } 
    // At this point, vars contains values of all variables assigned in commands 
    // from the command list 
} 

Оценки должно стать относительно простым:

private static Integer evaluate(Node node, Map<string,Integer> vars) { 
    if (node is an assignment) { 
     String varName = ... // get variable name from node 
     Node expr = ... // get the node representing expression being assigned 
     Integer value = evaluate(expr, vars); 
     vars.put(varName, value); 
     return value; 
    } 
    if (node is a variable reference) { 
     String varName = ... // get variable name from node 
     return vars.get(varName); 
    } 
    if (node is an integer constant) { 
     String constVal = ... // Get the representation from XML 
     return Integer.decode(constVal); 
    } 
    if (node is a binary expression) { 
     Node lhs = ... // Get the left-hand side expression from the node 
     Node rhs = ... // Get the right-hand side expression from the node 
     Integer lhsVal = evaluate(lhs, vars); 
     Integer rhsVal = evaluate(rhs, vars); 
     if (operator is plus) { 
      return new Integer(((int)lhsVal) + ((int)rhsVal)); 
     } 
     if (operator is minus) { 
      return new Integer(((int)lhsVal) - ((int)rhsVal)); 
     } 
     if (operator is multiply) { 
      return new Integer(((int)lhsVal) * ((int)rhsVal)); 
     } 
     if (operator is divide) { 
      return new Integer(((int)lhsVal)/((int)rhsVal)); 
     } 
     // ... and so on 
    } 
    // ... and so on 
}