transform flat linear tree representation into memory tree representation

Question

I have a string like this:

*b+a-aQa

and would like to transform it into an hierarchical tree structure like this:

The tree would consist of nodes like this:

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

Here expression would be, for example:

*

Terminal indicates if node is terminal node or not (b, a, a, a).

I am trying to come up with an algorithm to create the tree given the string. Any help would be very much appreciated. Thanks!

To provide more context this is related to this paper.

PS:

Another example:

Q*+-abcd

The meaning of this is as follows (Q = square root):

Answer 1

It's kind of like a binary heap, but not quite. You know the structure (0, 1, or 2 children) when you add a Node but you only read the children's content much later.

You can manage this with a Queue instead of a Stack

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

and you can call it like

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