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

本文关键字：结构 文本 何使用 递归 | 更新日期: 2023-09-27 18:22:23

我是C#的新手，我完全陷入了一个解析问题，我想使用递归，但我尝试这样做却一无所获。

我想在一个具有以下格式的文件中读取：

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

本质上，以冒号（：）结尾的行应该表示目录，而不以冒号结尾的行则应该表示其父目录中的文件，例如：fileA和fileG属于root目录、ileB、fileC，和fileF位于sub1目录中，依此类推（位置由缩进/空格确定）。

因此，我想以比目前更好的方式阅读这个文件，以及具有类似结构的更复杂的文件（for循环和if语句的可怕混乱）。我正在为目录和文件使用简单的自定义类（除了StreamReader之外，我没有使用.NET类逐行读取文本文件）

我曾经在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
   }         
}

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

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

我在解析布局风格或空格敏感语言方面没有太多经验，但根据我的经验，这样的任务不属于通常的解析解决方案。你至少要超越上下文无关的语言。

我决定将这个布局规则示例建模为二叉树。节点是行内容。向左下降表示保持相同的缩进级别，而向右下降表示增加缩进级别。

 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 { }
  }
}

从这里开始，我希望你能更清楚地为你的语言构建一个抽象的语法树。如果你想构建我提到的树，那么考虑保留一堆缩进级别。这需要一点思考，但我就交给你了。

让我们试试这个：

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?
        }
    }
}

此代码适用于您发布的文件：

     //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;
        }
    }

试试这个。由于您指定了深度，因此深度将参考空格/缩进。因此

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

从这里开始，我们已经知道了字符串前面的数字的深度。

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

相关文章：