java - postfijo - notacion prefija arboles

¿Cómo evaluar expresiones en este árbol?

Question

Aquí hay un ejemplo de un archivo xml analizado con el que estoy trabajando que lo etiqueta en forma de árbol

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]

Espero que esta entrada no sea difícil de entender. Esto es lo que parece normalmente cuando no se analiza desde un archivo XML:

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

etc ...

Todos los pares de asignación (es decir, un valor y una variable) deben almacenarse en un hashmap para que su variable pueda buscar el valor y usarlo en expresiones posteriores. Voy a usar un evaluador de descenso recursivo (¿creo?) Para resolver las expresiones de acuerdo con la gramática.

He buscado todo tipo de cosas en Google durante las últimas 24 horas y he visto muchos evaluadores de árbol para la aritmética básica (por ejemplo, 2 + 3 * 8, etc.) pero no he podido ver cómo funcionaría eso para mi específica árbol.

El código que he escrito hasta ahora es tan bajo como encontrar los nombres de las variables (a, b, c, d, e, etc.), pero no puedo comenzar a pensar en cómo codificar la recursión que proporcionará los valores correctos para el hash map.

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

Las clases de documento, nodo y lista de nodos para mi árbol son inusuales en el sentido de que no permiten un método ''getChild'' que creo que ahorraría mucho tiempo. Alguien sabe por qué es esto?

Problema realmente aleatorio aquí y espero que tenga sentido. Por favor, pídeme que explique todo lo que no esté claro y lo intentaré lo mejor que pueda. No busco a nadie que me resuelva el problema, simplemente me instruye sobre cómo decidir cómo codificar este algoritmo recursivo.

EDITAR: Además, la segunda ''entrada'' que puse arriba fue en realidad la salida. Debería haber sido esto:

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

Answer 1

Suponiendo que todos sus valores son de tipo entero, debe crear un HashMap<string,Integer> para almacenar los valores de las variables y pasarlo a su método de 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
}

La evaluación debería ser relativamente simple:

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
}