C# parsing custom hierarchical expression - build tree

Question

I'm building custom resource provider driven by very custom language. In order to do that I have to create tree data structure from custom expression. Let me explain:

f1(f2,f3,f6(f4),f5)

Above, is example of my custom expression , from which I want to build tree. Root - f1, has children : f2, f3, f4, f5. But f4 also has it's own children.

I've written solution for this problem, but I want to find better way to achieve this goal.

class Node
{
    public string val;
    public List<Node> child = new List<Node>();
}

private Node parseInput(string input, int index)
{
    string nodeName = findToken(input,ref index);
    Node tmp = new Node() { val = nodeName };
    tmp.child = expandNodes(input, ref index);
    return tmp;
}


private List<Node> expandNodes(string input, ref int index)
{
    List<Node> res = new List<Node>();
    while (!char.IsLetterOrDigit(input[index++]) && index < input.Length) ;
    index--;

    while (index < input.Length)
    {
        if (checkNext(input, index, ')'))
        {
            while (!char.IsLetterOrDigit(input[index++]) && index < input.Length) ;
            index--;
            return res;
        }
        Node tmp = new Node() { val = findToken(input,ref index) };
        if (checkNext(input, index, '('))
        {
            tmp.child = expandNodes(input, ref index);
        }
        res.Add(tmp);
    }


    return res;
}


private bool checkNext(string s, int index, char desiredChar)
{
    string vc = "" + s[index];
    while (index < s.Length && !char.IsLetterOrDigit(s[index]))
    {
        char chr = s[index];
        if (chr == desiredChar)
        {
            return true;
        }
        index++;
    }
    return false;
}


private string findToken(string s, ref int index)
{
    string res = null;
    while (!char.IsLetterOrDigit(s[index++]) && index < s.Length) ;
    index--;

    while (index < s.Length && char.IsLetterOrDigit(s[index]))
    {
        res += s[index];
        index++;
    }
    return res;
}

enter image description here

What kind of "better way" are you searching for ?

Florian F.
– Florian F.

2014-04-04 08:58:04 +00:00
Commented Apr 4, 2014 at 8:58 — Florian F.
– Florian F., Commented Apr 4, 2014 at 8:58
more efficient, more elegant algorithm

Kyniek
– Kyniek

2014-04-04 09:04:13 +00:00
Commented Apr 4, 2014 at 9:04 — Kyniek
– Kyniek, Commented Apr 4, 2014 at 9:04

Dmitrii Bychenko · Accepted Answer · 2014-04-04 09:27:23Z

I'd rather put Parse as a static method into the Node class:

    // Simplified implementation: some checks removed, many useful methods omitted
    public class Node {
      private String m_Title;
      private Node m_Parent;
      private List<Node> m_Items = new List<Node>();

      public Node(String title) {
        m_Title = title;
      }

      public Node Parent {
        get {
          return m_Parent;
        }
      }

      public IReadOnlyList<Node> Items {
        get {
          return m_Items;
        }
      }

      public void Add(Node value) {
        m_Items.Add(value);

        value.m_Parent = this;
      }

      public String Title {
        get {
          return m_Title;
        }
      }

      public override String ToString() {
        if (m_Items.Count <= 0)
          return m_Title;

        StringBuilder Sb = new StringBuilder();

        Sb.Append(m_Title);

        Sb.Append("(");

        for (int i = 0; i < m_Items.Count; ++i) {
          Sb.Append(m_Items[i].ToString());

          if (i < m_Items.Count - 1)
            Sb.Append(",");
        }

        Sb.Append(")");

        return Sb.ToString();
      }

      public static Node Parse(String value) {
        Node owner = null; 
        Node current = null;

        StringBuilder Sb = new StringBuilder();

        foreach (Char ch in value) {
          if (Char.IsLetterOrDigit(ch))
            Sb.Append(ch);
          else {
            if (Sb.Length > 0) {
              current = new Node(Sb.ToString());

              Sb.Length = 0;

              if (owner != null)
                owner.Add(current);
              else
                owner = current;
            }

            if (ch == '(') 
              owner = current;
            else if (ch == ')' && (owner.Parent != null)) 
              owner = owner.Parent;
          }
        }

        // Tail 
        if (Sb.Length > 0) {
          current = new Node(Sb.ToString());

          Sb.Length = 0;

          if (owner != null)
            owner.Add(current);
          else
            owner = current;
        }

        return owner;
      }
    }

...

  Node test = Node.Parse("f1(f2,f3,f6(f4),f5)");
  String check = test.ToString(); // <- "f1(f2,f3,f6(f4),f5)"

Florian F. · Accepted Answer · 2014-04-04 11:52:26Z

I would have gone with regex matching and recursive call, something like :

class Node {
    public string val;
    public List<Node> children = new List<Node>();

    public static Node Parse(string input) {
        Node n = new Node();

        //extract value and children
        Regex reg = new Regex("(?<val>\\w+)(?:\\((?<children>(?:\\([^()]*\\)|.)*)\\))?");

        // fill value
        Match match = reg.Match(input);
        n.val = match.Groups["val"].Value;

        // if children group matched
        if (match.Groups["children"].Success) { 
            // split through commas outside of parenthesis
            string[] childrenTab = Regex.Split(match.Groups["children"].Value, ",(?![^(]*\\))");
            // and call recursively for each child
            foreach (string child in childrenTab) {
                n.children.Add(Node.Parse(child));
            }
        }
        return n;
    }

Also, the static method seems more appropriated.

Collectives™ on Stack Overflow

C# parsing custom hierarchical expression - build tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related