如何评估这棵树中的表达式？

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

所有的赋值对（即一个值和一个变量）都将被存储在哈希映射表中，这样值就可以通过它的变量进行查找，并在随后的表达式中使用。我需要使用递归下降求值器（我想是这个？）根据语法来解决表达式。

我已经搜索了各种各样的东西，过去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”方法，我认为这会节省很多时间。有人知道为什么吗？

真的是一个很随机的问题，我希望我的表述有意义。如果有不清楚的地方，请告诉我，我会尽力解释。我不是要求别人来解决我的问题，而只是想指导我如何编写这个递归算法。

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

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

- Chucky

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
}

- Sergey Kalinichenko

---

我应该说，当函数涉及到set、tuple等情况时，a、b、c、d后面的代码会变得更加复杂。不过，我会尝试你给我的代码，它看起来布局很好！ - Chucky