3

我有一个轻微的算法问题。我想我错过了一些东西，但不能完全弄清楚是什么。

我想走到一棵包含字符串的树上，然后拿出一个唯一的字符串。

这是我要解析的树的图形示例。

树示例

我的树将具有三种不同类型的元素：

  • 布尔运算符（OR、NOT、AND）=> BE
  • 其他运算符（如 =）=> QO
  • 叶子（最后一个元素）=> LEAF

我想结束这样的事情：

"LEAF QO LEAF BE LEAF QO LEAF "

现在，我使用递归方法：我检查树的当前元素，并根据我拥有的元素类型在其子元素上重新运行该方法。对于每一步，我都会填充我的最终字符串。

公共类 SingleTest { static String[] booleanElements = {"or", "and", "not"};

public static void main(String[] args) throws Exception {
    CommonTree tree = (CommonTree)parser.parse().getTree();

    if(true){
        String where = "";
        printWhere(tree, where);
        System.out.println(where);
    }       

}   

/*
 * Print to where tests
 */
public static boolean isBooleanElement(CommonTree t){
    return Arrays.asList(booleanElements).contains(t.toString().toLowerCase());
}


public static String printWhere(CommonTree t, String where){
    //---------------------
    // Checking node type
    //---------------------

    // Boolean Element 
    if (isBooleanElement(t)){
        // Continue parsing the tree                
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            printWhere((CommonTree)t.getChild(i), where+ "BE");
        }               
    }

    // Last element of tree (LEAF)
    else if(t.getChildCount() == 0 ){
        where = where + "LEAF";
    }

    // query operator
    else{
        // Continue parsing the tree    
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            printWhere((CommonTree)t.getChild(i), where + "QO");
        }                   
    }

    //---------------------
    return where;
}

我的问题是这段代码：

        String where = "";
        System.out.println(printWhere(tree, where));

返回“”（由于我的实现，这是合乎逻辑的）。

所以我的问题是，我怎样才能将非 void 字符串作为最终输出？

希望这足够清楚谢谢您的帮助

请注意，此类仅用于测试目的，我知道将 static 放在任何地方都是不好的做法 :)

编辑 ：

问题是（如预期的那样）由于我缺乏递归经验。这是我的最终代码：

public static String printWhere(CommonTree t, String where){
    //---------------------
    // Checking node type
    //---------------------

    // Boolean Element 
    if (isBooleanElement(t)){
        // Continue parsing the tree                
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            where = printWhere((CommonTree)t.getChild(i), where) + "BE";
        }               
    }

    // Last element of tree (LEAF)
    else if(t.getChildCount() == 0 ){
        where = where + "LEAF";
    }

    // query operator
    else{
        // Continue parsing the tree    
        for ( int i = 0; i < t.getChildCount(); i++ ) {
            where = printWhere((CommonTree)t.getChild(i), where ) + "QO";
        }                   
    }

    //---------------------
    return where;
}
4

1 回答 1

3

问题是你的方法printWhere没有返回任何东西！您将值附加到新where字符串，但由于 Java 按值传递参数，因此当您离开该方法时，这个新创建的字符串将被丢弃。

使此方法返回字符串并where在其末尾返回。然后，将递归调用的结果与上一级的字符串连接起来。这就是递归的工作原理。

于 2012-05-21T09:12:07.640 回答