这是一个解析过的 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)};
等...
所有赋值对(即一个值和一个变量)都将存储在 HashMap 中,以便可以通过它的变量查找该值并在以后的表达式中使用。我要使用递归下降求值器(我想?)根据语法来解决表达式。
我在过去 24 小时内用谷歌搜索了各种各样的东西,看到了很多基本算术的树求值器(例如 2 + 3 * 8 等),但还没有看到它是如何工作的对于我的特定树。
到目前为止,我编写的代码低至找到变量名称(a、b、c、d、e 等),但我无法开始考虑如何编写递归代码以提供正确的 HashMap 的值。
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));
最佳答案
假设你所有的值都是整数类型,你应该创建一个 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
}
关于java - 如何评估这棵树中的表达式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9214836/