Java – how do I evaluate expressions in this tree?

The following is an example of the parsed XML file I'm using, which marks it as a tree

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]

I hope this input is not difficult to understand The following is a normal case when it is not parsed from an XML file:

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

Wait

All assignment pairs (i.e. values and variables) are stored in the hash map so that the value can be found through its variables and used in subsequent expressions I will use the recursive descent calculator (I think?) To solve the expression according to the syntax

I have searched all kinds of things in the past 24 hours and have seen many tree evaluators for basic arithmetic (such as 2, 3 * 8, etc.), but I haven't seen any use for my specific tree

So far, the code I've written is as low as finding variable names (a, B, C, D, e, etc.), but I can't start thinking about how to write recursion, which will provide the correct value for it Hash mapping

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

The document, node and node list classes of my tree are unusual because they do not allow the 'getchild' method, which I think can save a lot of time Who knows why?

This is really a random problem. I hope it makes sense Please let me elaborate on anything unclear, and I'll do my best I'm not looking for anyone to solve the problem for me, but just guide me how to decide how to code this recursive algorithm

Editor: in addition, the second "input" I mentioned above is actually output It should be like this:

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

Solution

Assuming that all your values are of integer type, you should create a HashMap < string, integer > to store the variable value and pass it to the evaluate method:

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
}

The assessment should be relatively 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
}