基于符号元数在C#中从符号列表构建树的实现方法

问题背景 #

我需要从一组具有不同元数（Arity）的符号列表构建树形结构，示例如下：

符号元数定义 #

输入字符串与目标树 #

输入字符串为 AABCDDEEDED，需要构建的树形结构如下：

A
     / \
    A   B
   / \  |
  C   D D
 / \
E   E

注：字符串末尾的DED无需使用，因为树已构建完成。

我已定义好带元数的符号类，所有符号实现ISymbol<T>接口，包含存储子符号的属性，也能生成对应的字符串序列，但不清楚如何实现树的构建逻辑，同时想知道这种树是否有特定名称。

树的类型说明 #

这种结构属于前缀表达式（波兰表达式）对应的抽象语法树（Abstract Syntax Tree, AST），本质是表达式树的一种变体。构建方式是按层序维护待填充子节点的节点（用队列实现），优先填满当前节点的所有子节点后，再处理下一个需要填充的节点。

实现代码（C#） #

基于建议实现的构建代码如下：

var root = GeneCoding![0] as Symbol<T>;
if (root!.Arity == 0)
{
    return root!;
}

var queue = new Queue<Symbol<T>>();
queue.Enqueue(root);

Symbol<T> node;
Symbol<T> current;

foreach (var symbol in GeneCoding!.Skip(1))
{
    node = (Symbol<T>)symbol;
    if (node.Arity != 0)
    {
        queue.Enqueue(node);
    }

    current = queue.Peek();
    current.Nodes.Add(node);
    if (current.Arity == current.Nodes.Count)
    {
        var dequeued = queue.Dequeue();
        if (queue.Count > 0)
        {
            queue.Enqueue(dequeued);
        }
        else
        {
            return dequeued;
        }
    }
}

throw new Exception();

代码逻辑说明 #

• 初始化根节点：取符号列表的第一个元素作为树的根节点，若根节点是0元符号（无子女），直接返回。
• 队列维护待填充节点：用队列存储需要填充子节点的符号，初始时将根节点入队。
• 遍历剩余符号构建子节点：
  1. 遍历每个后续符号，将其转为Symbol<T>类型；若该符号有元数（非0），则入队等待填充它的子节点。
  2. 将当前符号添加到队列头部节点的子节点列表中。
  3. 当队列头部节点的子节点数量达到其元数时，将该节点出队；若队列仍有元素，将出队的节点重新入队；若队列已空，说明树构建完成，返回该节点。
• 异常处理：若遍历完所有符号仍未完成树的构建，抛出异常。

内容的提问来源于stack exchange，提问作者Dominick