如何使用递归将文本解析为树结构？

Question

我是C＃的新手，我完全停留在解决问题的地方，我想使用递归，但是我尝试这样做却让我无处可寻。

我想有以下格式的文件阅读：

root: 
    fileA 
    sub1: 
     fileB 
     fileC 
     sub2: 
     fileD 
     fileE 
     fileF 
    fileG 
    sub3: 
     fileH 

本质上说，结束冒号（行:)应该代表目录和不冒号结束线应该以代表他们的父目录文件，例如：的fileA和fileG属于在根目录，FILEB，fileC，并fileF位于子目录目录内，依此类推（位置由缩进/空格确定）。因此，我想读取这个文件，以及更复杂的文件，其结构类似于我目前正在做的（对于循环和if语句来说是一个可怕的混乱）。我为目录和文件使用简单的自定义类（我没有使用.NET类，除了StreamReader逐行读取文本文件）

我在python中做过类似的事情，但由于某种原因，我无法包装我的头在如何在C＃中做到这一点，这是愚蠢的，因为这是一个抽象的问题，特定于语言的实现不应该太重要。我想，重要的是我缺乏对如何在这些情况下最好地应用递归的理解。我在正确的轨道上吗？我只是觉得有一种更加优雅的方式来解析这个文件到我自定义的类中（在示例文本中保留一个树结构），我认为递归是答案。我只是看不到它。

任何帮助，将不胜感激，即使它不是一个答案，更猛烈的推动在正确的方向。或轻轻推动。

示例代码在C＃中尝试使用递归（不完整的，但我希望它得到跨什么，我试图做）：

public void buildDirectoryFromFile(string file) 
{ 
    string line; 
    StreamReader data = new StreamReader(file);   

    int depth = 0; 
    while ((line = data.ReadLine()) != null) 
    { 
     depth = line.Length - line.TrimStart(' ').Length; 
     parseTextIntoTree(line, depth); 
    }    
} 


public void parseTextIntoTree(string line, int depth) 
{  
    if (line.Contains(':')) 
    { 
     //Totally lost  
    } 
    else 
    { 
     //Totally lost 
    }   
} 

深度在这种情况下指的是空格/缩进。字符串和左边距之间的空间越多，它在树中的'越深'。

Answer 1

让我们试试这个：

public void buildDirectoryFromFile(string file) 
{ 
    string line; 
    StreamReader data = new StreamReader(file);   

    List<string> lines = new List<string>(); 
    while ((line = data.ReadLine()) != null) 
    { 
     lines.Add(line); 

    }  
    int lineProcessed = 0; 
    ParseTextIntoTree(lines, ref lineProcessed, 0);   
} 

public const int PadCount = 3; // Your padding length in text file 

public void ParseTextIntoTree(List<string> lineList, ref int lineProcessed, int depth) 
{ 
    while(lineProcessed < lineList.Count) 
    { 
     string line = lineList[lineProcessed++]; 
     int lineDepth = line.Length - line.TrimStart(' ').Length; 

     if(lineDepth < depth) 
     { 
      // If the current depth is lower than the desired depth 
      // end of directory structure is reached. Do backtrack 
      // and reprocess the line in upper depth 
      lineProcessed--; 
      return; 
     } 

     if(line.EndsWith(":")) 
     { 
      // Do something, perhaps create directory? 
      ParseTextIntoTree(lineList, ref lineProcessed, depth + PadCount); 
     } 
     else 
     { 
      // Do something, perhaps create file? 
     } 
    } 
} 

Answer 2

我没有与解析布局风格或空格敏感的语言太多经验，但是从我都经历过这样的任务不按照通常的解析方案下降。你至少必须超越上下文无关的语言。

我决定对这个布局规则的例子进行建模的方式就像是一棵二叉树。节点是行内容。下降到左边表示保持相同的缩进级别，而下降到右侧表示增加缩进级别。

root 
/ \ 
ε fileA 
/ \ 
    sub1: ε 
    | \___ 
    |  | 
    fileG  fileB – ε 
    |   |  
    sub3:  fileC – ε 
    | \  | 
    ε fileH sub2: —+ 
      |  | 
      fileF fileD 
        | 
        fileE 

我已经将源文件建模为这样一棵树。你还会注意到，就行顺序而言，树下降到右边第一个，然后左边第二个。

我们现在有一种方式可以用任何语言解析工具来解析与布局样式不同的大括号样式的源代码。例如，假设我们想要生成令牌以供解析器使用。随着你的直觉暗示，这可以很容易地递归地完成。

1. 发出根节点的标记（如果节点是ε，那么我们不会发出标记）。
2. 发出一个大括号，然后在右子树上递归。
3. 发出一个大括号，然后递归左子树。

在树遍历方面，这接近于从右到左的顺序。但是，我们也正在添加一个紧凑大括号。

我现在按照这个算法来标记这个例子。为了简单起见，我只是使用原始源中的名称作为标记名称，并且还添加{和}作为标记。

(recursion_depth.step_number) 
(1.1) root 
(1.2) root { 
(2.1) root { fileA 
(2.2) root { fileA { 
(2.3) root { fileA { } 
(3.1) root { fileA { } sub1: 
(3.2) root { fileA { } sub1: { 
(4.1) root { fileA { } sub1: { fileB 
etc. 

最后到达（格式为清楚起见）

root { 
    fileA { } 
    sub1: { 
    fileB { } 
    fileC { } 
    sub2: { 
     fileD { } 
     fileE { } 
    } 
    fileF { } 
    } 
    fileG { } 
    sub3: { 
    fileH { } 
    } 
} 

在这里，我希望这是更清晰了如何构建一个抽象语法树为您的语言。如果你想构建我提到的树，然后考虑保留一堆缩进级别。这需要一些思考，但我会让你知道的。

Answer 3

该代码可以使用您发布文件：

 //The top-level Node 
    TreeNode root; 

    //Temp value for processing in parseTextIntoTree 
    TreeNode ParentNode; 

    //Temp value for processing in parseTextIntoTree 
    int actualdepth = -1; 

    //The depth step between two layers 
    int depthdifference = 3; 

    public void buildDirectoryFromFile(string file) 
    { 
     string line; 
     StreamReader data = new StreamReader(file); 

     int depth = 0; 
     while ((line = data.ReadLine()) != null) 
     { 
      depth = line.Length - line.TrimStart(' ').Length; 
      parseTextIntoTree(line, depth); 
     } 

     this.treeView1.Nodes.Add(root); 
    } 

    public void parseTextIntoTree(string line, int depth) 
    { 
     //At the beginning define the root node 
     if (root == null) 
     { 
      root = new TreeNode(line); 
      ParentNode = root; 
      actualdepth = depth; 
     } 
     else 
     { 
      //Search the parent node for the current depth 
      while (depth <= actualdepth) 
      { 
       //One step down 
       ParentNode = ParentNode.Parent; 
       actualdepth -= depthdifference; 
      } 

      ParentNode = ParentNode.Nodes.Add(line.Trim()); 
      actualdepth = depth; 
     } 
    } 

Answer 4

试试这个。既然你指定的深度将指空间/缩进。因此

TreeStruc = @"root: 
       fileA 
       sub1: 
        fileB 
        fileC 
        sub2: 
        fileD 
        fileE 
        fileF 
       fileG 
       sub3: 
        fileH"; 
TreeStruc = Regex.Replace(TreeStruc, " ", "-"); 
TreeStruc = Regex.Replace(TreeStruc, "---", "-"); 
using(StringReader reader = new StringReader(TreeStruc)) 
{ 
    string line; 
    while((line = reader.ReadLine()) != null) 
    { 
     int cnt = line.Count(f => f == '-'); 
     String str2Replace = new String('-', cnt); 
     line = Regex.Replace(line, str2Replace == "" ? "-" : str2Replace, cnt.ToString() + "~ "); 
     updatedTreeStruc = updatedTreeStruc + line + "\n"; 
    } 
} 

它会表现出如下结果：

root: 
1~ fileA 
1~ sub1: 
2~ fileB 
2~ fileC 
2~ sub2: 
3~ fileD 
3~ fileE 
2~ fileF 
1~ fileG 
1~ sub3: 
2~ fileH 

现在，从这里我们已经知道的深度是在字符串前面的数字。

以同样的方式，我们可以分析字符串是文件夹还是文件。