我有一个像这样的字符串:

*b+a-aQa


并希望将其转换为这样的分层树结构:

c# - 将平面线性树表示转换为内存树表示-LMLPHP

该树将由以下节点组成:

public class TreeNode : ITreeNode
{
    public string Expression { get; set; }
    public bool Terminal { get; set; }
        public List<ITreeNode> Children { get; set; }
}

public interface ITreeNode
{
    string Expression { get; set; }
    bool Terminal { get; set; }
    List<ITreeNode> Children { get; set; }
}


例如,此处的表达式为:

*

终端指示节点是否为终端节点(b,a,a,a)。

我试图提出一种算法来创建给定字符串的树。任何帮助将不胜感激。谢谢!

为了提供更多上下文,这与此paper有关。

PS:

另一个例子:

Q*+-abcd


c# - 将平面线性树表示转换为内存树表示-LMLPHP

其含义如下(Q =平方根):

c# - 将平面线性树表示转换为内存树表示-LMLPHP

最佳答案

有点像二进制堆,但不完全是。添加节点时,您知道结构(0、1或2个子代),但是稍后才读取子代的内容。

您可以使用队列而不是堆栈来管理

private static Node Parse(TextReader reader)
{
    var nodes = new Queue<Node>();

    var root = new Node();
    nodes.Enqueue(root);

    int ch;

    while ((ch = reader.Read()) != -1)
    {
        char token = (char)ch;

        // syntax check 1: the queue should not be empty
        var node = nodes.Dequeue();
        node.Symbol = token;

        if ("Q".IndexOf(token) >= 0)
        {
            node.Left = new Node();
            nodes.Enqueue(node.Left);
        }
        else if ("+-*".IndexOf(token) >= 0)
        {
            node.Left = new Node();
            nodes.Enqueue(node.Left);
            node.Right = new Node();
            nodes.Enqueue(node.Right);
        }
        // else : 0 children
    }

    // syntax check 2: the queue should now be empty
    return root;
}


你可以这样称呼它

var tree = Parse(new StringReader("Q*+-abcd"));

关于c# - 将平面线性树表示转换为内存树表示,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49551680/

10-10 21:50