How to evaluate expressions in this tree?

Question

Here is an example of the parsed XML file I'm working with so that it embeds it in a tree form

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 that this input is not difficult to understand. Here is what it usually looks like when not being parsed from an XML file:

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

etc...

All destination pairs (i.e., value and variable) must be stored in a hash map so that the value can be viewed by this variable and used in subsequent expressions. I have to use a recursive descent evaluator (I think?) To resolve expressions according to grammar.

Over the past 24 hours, I have been looking for all kinds of things and have seen many tree evaluators for basic arithmetic (e.g. 2 + 3 * 8, etc.), but I have not been able to see how this will work for my particular tree.

The code I wrote so far is as low as searching for variable names (a, b, c, d, e, etc.), but I can't figure out how to encode a recursion that will provide the correct values ​​for hash cards.

 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, the node and nodelist classes for my tree are unusual in that they do not allow the use of the getChild method, which, I think, will save a lot of time. Does anyone know why this is?

A really random issue here, and I hope this made sense. Please ask me to tell you something that is unclear, and I will try to do everything in my power. I am not looking for anyone to solve this problem for me, but simply instruct me on how to solve how to code this recursive algorithm.

EDIT: Also, the second “enter” that I set above was actually an exit. It should be like this:

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

Answer 1

Assuming all your values ​​are of integer type, you should create a HashMap<string,Integer> to store the values ​​of the variables 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 become 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 }