.NET Custom hierarchical expression to treeview data structure


I’m not good at English. It’s gonna be hard to read. I apologize in advance.

I need expression parser for draw diagram(fault tree). In order to do that I have to create data structure from custom expression

( (123-A1) AND (123-A2) AND (123-A3) OR (123-A4 AND (123-A5 OR 123-A6)) ) 

The above example was written roughly as I thought.

  1. In some cases, parentheses are used for each variable for readability.
  2. Read in order within the same parentheses.
  3. Read in order if there are no parentheses.
  4. Parentheses around the expression can be attached without meaning.
  5. Operators use only AND, OR parentheses use only (, ).
  6. I don’t know which is the best way string to data structure.
  7. The depth and order of parentheses and.. anything are all important because eventually I need to draw Diagram.
           _________OR___________           |                      |           |                 ____AND____           |                |           |            ______AND______         |       ___OR___    |       |       |        |      |        | 123-A1  123-A2  123-A3  123-A4  123-A5  123-A6 

Expression to Token

public class Token {     public TokenType Type;  // Operator, Parenthesis, Variable      public string Label;     public int Depth;     public int Group;      public Token(string label)     {         Label = label.Trim();          if (ExpressionParser.SupportedOperatorHashSet.Contains(label.ToUpper()))         {             Type = TokenType.Operator;         }         else if (ExpressionParser.SupportedParenthesesHashSet.Contains(label))         {             Type = TokenType.Parenthesis;         }         else         {             Type = TokenType.Variable;         }     } }  public enum TokenType {     Variable,     Operator,     Parenthesis }  public static class ExpressionParser {     private static Regex TokenRegex = new Regex(@"[\(\)]|[\d\w-]+");      internal static readonly HashSet<string> SupportedOperatorHashSet = new HashSet<string>() { AndGate, OrGate };     internal static readonly HashSet<string> SupportedParenthesesHashSet = new HashSet<string>() { OpenParenthesis, CloseParenthesis };     private static readonly List<Token> TokenList = new List<Token>();      internal const string AndGate = "AND";     internal const string OrGate = "OR";     internal const string OpenParenthesis = "(";     internal const string CloseParenthesis = ")";      public static List<Token> Parse(string expression)     {         try         {             // Get '(' ')' '123-A1' 'AND' 'OR'             MatchCollection matches = TokenRegex.Matches(expression); // @"[\(\)]|[\d\w-]+"             int depth = 0;              foreach (Match match in matches)             {                 Token token = new Token(match.Value);                 TokenList.Add(token);                  // Increase depth when token is open parenthesis                  if (token.Type == TokenType.Parenthesis && token.Label == OpenParenthesis)                 {                     depth += 1;                 }                  token.Depth = depth;                  // Set group                 if (TokenList.Count > 1)                 {                     Token prevToken = TokenList[TokenList.Count - 2];                     if (prevToken.Depth == token.Depth)                     {                         token.Group = prevToken.Group;                     }                     else                     {                         token.Group = prevToken.Group + 1;                     }                 }                  // Decrease depth after token is close parenthesis                  if (token.Type == TokenType.Parenthesis && token.Label == CloseParenthesis)                 {                     depth -= 1;                 }             }              // Remove parenthesis  [ex. (123-ab)]             for (int i = 0; i < TokenList.Count; i++)             {                 if (i + 2 < TokenList.Count &&                     TokenList[i].Type == TokenType.Parenthesis && TokenList[i].Label == OpenParenthesis &&                     TokenList[i + 2].Type == TokenType.Parenthesis && TokenList[i].Label == CloseParenthesis)                 {                     TokenList.RemoveAt(i + 2);                     TokenList.RemoveAt(i);                 }             }              return new List<Token>(TokenList);         }         finally         {             TokenList.Clear();         }     } } 

Run

ExpressionParser.Parse("( (123-A1) AND (123-A2) AND (123-A3) OR (123-A4 AND (123-A5 OR 123-A6)) )"); 

Result

OR  ├ AND  │  ├ 123-A1  │  ├ 123-A2  │  └ 123-A3  └ AND     ├ 123-A4     └ OR       ├ 123-A5       └ 123-A6