如何使用递归解析Java中的组内组？

Question

我刚开始接触递归，所以如果有人能提供帮助，我将不胜感激。

我有以下 String:

field1: typeA
field2: typeA
field3: typeB
group1:
    fieldA: typeA
    fieldB: typeB
    subGroup1:
        fieldX: typeB
        fieldY: typeB
    fieldC: typeC
field4: typeA
group2:
    fieldA: typeB
    subGroup1:
        fieldX: typeA
        fieldY: typeA
    fieldB: typeA
    fieldC: typeC
field5: typeC
field6: typeD

请注意，我可以在组（子组）中设置组。我也可以在组内组内组，所以据我所知递归是强制性的。

请注意，每行开头的间距决定该字段是否属于该组。

我想在 Java 中编写一个方法，它将 return 一个 LinkedHashMap<String, Object>，其中 Object 映射值可以是一个 String 表示这是一个字段（不是一个组）或另一个 LinkedHashMap<String, Object> 表示这是一个组（不是一个字段）。

我试过但惨败。递归目前对我来说太难了，但我正在研究它。

想帮谁就帮谁，代码下方：

    public static void main(String[] args) {
        
        String text = String.join("\n",
                
                "field1: typeA",
                "field2: typeA",
                "field3: typeB",
                "group1:",
                "    fieldA: typeA",
                "    fieldB: typeB",
                "    subGroup1:",
                "        fieldX: typeB",
                "        fieldY: typeB",
                "    fieldC: typeC",
                "field4: typeA",
                "group2:",
                "    fieldA: typeB",
                "    subGroup1:",
                "        fieldX: typeA",
                "        fieldY: typeA",
                "    fieldB: typeA",
                "    fieldC: typeC",
                "field5: typeC",
                "field6: typeD",
                
                "");
        
        Map<String, Object> solution = doIt(text);
        System.out.println(solution);
    }
    
    private static LinkedHashMap<String, Object> doIt(String text) {
        // solution goes here...
        return null;
    }
}

这是正确的输出：

public static void main(String[] args) {
    Map<String, Object> map = new LinkedHashMap<String, Object>();
    
    map.put("field1", "typeA");
    map.put("field2", "typeA");
    map.put("field3", "typeB");
    
    Map<String, Object> map2 = new LinkedHashMap<String, Object>();
    map2.put("fieldA", "typeA");
    map2.put("fieldB", "typeB");
    
    Map<String, Object> map3 = new LinkedHashMap<String, Object>();
    map3.put("fieldX", "typeB");
    map3.put("fieldY", "typeB");
    map2.put("subGroup1", map3);
    
    map2.put("fieldC", "typeC");
    
    map.put("group1", map2);
    
    map.put("field4", "typeA");
    
    Map<String, Object> map4 = new LinkedHashMap<String, Object>();
    map4.put("fieldA", "typeB");
    
    Map<String, Object> map5 = new LinkedHashMap<String, Object>();
    map5.put("fieldX", "typeA");
    map5.put("fieldY", "typeA");
    map4.put("subGroup1", map5);
    
    map4.put("fieldB", "typeA");
    map4.put("fieldC", "typeC");
    
    map.put("group2", map4);
    
    map.put("field5", "typeC");
    map.put("field6", "typeD");
    
    System.out.println(map);
}

输出：

{field1=typeA, field2=typeA, field3=typeB, group1={fieldA=typeA, fieldB=typeB, subGroup1={fieldX=typeB, fieldY=typeB}, fieldC=typeC}, field4=typeA, group2={fieldA=typeB, subGroup1={fieldX=typeA, fieldY=typeA}, fieldB=typeA, fieldC=typeC}, field5=typeC, field6=typeD}

Answer 1

我会构建一个 Queue 来保存您的文本行。队列由您的函数使用，每次检测到新组时都会递归。使用队列允许您在每一行 peek ，因此当您找到当前组的末尾时，通过检查缩进级别，您可以 return 并让前一个调用处理剩余字段。

static String INDENT = "    ";

static LinkedHashMap<String, Object> doIt(Queue<String> q, String ind) 
{
    LinkedHashMap<String, Object> map = new LinkedHashMap<>();
    
    while(!q.isEmpty())
    {
        String line = q.peek();
        
        if(!line.startsWith(ind)) break;
        
        q.poll();
        
        int idx = line.indexOf(":");
        String name = line.substring(ind.length(), idx);
        String value = line.substring(idx+1).trim();
        
        if(!value.isEmpty())
            map.put(name, value);
        else
            map.put(name, doIt(q, ind + INDENT));
    }
    
    return map;
}

测试：

String text = String.join("\n",
  
  "field1: typeA",
  "field2: typeA",
  "field3: typeB",
  "group1:",
  "    fieldA: typeA",
  "    fieldB: typeB",
  "    subGroup1:",
  "        fieldX: typeB",
  "        fieldY: typeB",
  "    fieldC: typeC",
  "field4: typeA",
  "group2:",
  "    fieldA: typeB",
  "    subGroup1:",
  "        fieldX: typeA",
  "        fieldY: typeA",
  "    fieldB: typeA",
  "    fieldC: typeC",
  "field5: typeC",
  "field6: typeD",
  
  "");

Map<String, Object> solution = doIt(new LinkedList<String>(Arrays.asList(text.split("\n"))), "");
print(solution, "");

print 方法如下所示（请注意，由于转换不安全，我们必须禁止显示警告）：

@SuppressWarnings("unchecked")
static void print(Map<String, Object> map, String ind)
{
    for(String name : map.keySet())
    {
        Object value = map.get(name);
        if(value instanceof String)
            System.out.println(ind + name + ": " + value);
        else
        {
            System.out.println(ind + name + ":");
            print((Map<String, Object>)value, ind + INDENT);
        }           
    }
}

输出：

field1: typeA
field2: typeA
field3: typeB
group1:
    fieldA: typeA
    fieldB: typeB
    subGroup1:
        fieldX: typeB
        fieldY: typeB
    fieldC: typeC
field4: typeA
group2:
    fieldA: typeB
    subGroup1:
        fieldX: typeA
        fieldY: typeA
    fieldB: typeA
    fieldC: typeC
field5: typeC
field6: typeD

如何使用递归解析Java中的组内组？

How to use recursion to parse groups inside groups in Java?

java

recursion

data-structures