如何评估树中的表达式?
问题描述:
这是我与它的标签加工成树的形式如何评估树中的表达式?
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文件的例子。这里是什么样子时,通常不从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”的方法,我认为将节省大量的时间。有人知道这是为什么吗?
这里真的是随机问题,我希望它有道理。请让我详细说明任何不清楚的事情,我会尽我所能。我不是在寻找任何人来解决这个问题,而只是告诉我如何决定如何编码这个递归算法。
编辑: 此外,我上面提到的第二个'输入'实际上是输出。它应该是这样的:
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
}
我应该说,a,b,c和d之后的行在涉及函数时会变得更复杂一些,比如set,元组等,我会尝试你给我的东西,但它看起来像一个很好的布局! – Chucky 2012-02-09 18:47:28