C＃解析自定義分層表達式 - 構建樹

Question

我正在構建由非常自定義的語言驅動的自定義資源提供程序。爲了做到這一點，我必須從自定義表達式創建樹數據結構。讓我解釋一下：

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

上面是我的自定義表達式的例子，我想從中構建樹。根 - f1，有子女：f2，f3，f4，f5。但f4也有它自己的孩子。

我已經爲這個問題寫了解決方案，但我想找到更好的方法來實現這個目標。

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

Answer 1

我寧願把Parse爲靜態方法到Node類：

// 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)" 

Answer 2

我會去用正則表達式匹配和遞歸調用，東西如：

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

此外，靜態方法似乎更適用。