如何评估树中的表达式？

Question

这是我与它的标签加工成树的形式

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文件的例子。这里是什么样子时，通常不从XML文件解析：

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

等等

全部转让对（即，一个值和变量）将被存储在一个哈希映射，以便该值可以通过它的变量查找并在以后的表达式中使用。我将使用递归下降评估器（我认为？）根据语法解决表达式。

我在过去的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); 

文件，节点和节点列表类我的树是不寻常的，他们不允许“getChild”的方法，我认为将节省大量的时间。有人知道这是为什么吗？

这里真的是随机问题，我希望它有道理。请让我详细说明任何不清楚的事情，我会尽我所能。我不是在寻找任何人来解决这个问题，而只是告诉我如何决定如何编码这个递归算法。

编辑： 此外，我上面提到的第二个'输入'实际上是输出。它应该是这样的：

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 
}