2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Please add to your question whether and if so which aspects of the code (e.g. style, best practices, performance, ...) the reviewers should focus on. This will likely help you to get feedback that's more relevant to you. \$\endgroup\$ – AlexV Apr 8 at 11:25
2
\$\begingroup\$

There are several problems with this code:

  • There's no syntax validation:
    • "))a" results in tokens with negative depth. It should be rejected as invalid.
    • "a AND b c" is not rejected either. Note the missing operator between b and c.
    • "a && b" results in only two tokens, a and b. The invalid && part is ignored. I'd expect such input to be rejected.
  • The removal of superfluous parenthesis is problematic:

    • It's broken (you're missing a + 2 somewhere).
    • It doesn't fix up the depth and group of subsequent tokens.
    • It doesn't handle multiple levels, so it simplifies "(((a)))" to "((a))" instead of to "a".
  • Why does the Token constructor determine the token type? Why not let ExpressionParser.Parse determine the type, and pass it in via Token's constructor?

  • Marking fields as readonly prevents them from being reassigned, but it won't make a mutable object immutable. Other code in the same assembly can break the parser by calling ExpressionParser.SupportedOperatorHashSet.Clear().
  • Why does Parse store its results in a static field (TokenList) instead of using a local variable? I don't see any advantage to this (but several disadvantages).
  • Why not expand TokenType with ParenthesisOpen, ParenthesisClose, AndOperator and OrOperator? That lets you simplify several checks.

What you have written is a lexer, not a parser. Instead of assigning a depth and group number to each token, consider parsing the resulting list of tokens into an actual tree structure. One way to do that would be to use the Shunting Yard algorithm. The resulting structure would consist of expression nodes, with variable nodes containing the name of a variable, and operation nodes containing an operator (and/or) and a list of operand expressions (which are either variable or operation nodes).

For example, "a AND (b OR c)" would produce the same result as:

new Operation(
    Operator.And,
    new Expression[] {
        new Variable("a"),
        new Operation(
            Operator.Or,
            new Expression[] {
                new Variable("b"),
                new Variable("c")
            })
    });

Parenthesis influence how this tree is created, but they don't need to be stored in the tree. Groups can be found by looking for Operation nodes, and depth is determined by how many Operation 'parents' a node has.

\$\endgroup\$
  • \$\begingroup\$ Thank you. I know most of the problems you're talking about. I've re-developed it a lot to implement this function, so I've made it simple. "Instead of assigning a depth and group number to each token, consider parsing the resulting list of tokens into an actual tree structure." This is the biggest problem for me. Please advise me on this part. \$\endgroup\$ – thecco Apr 9 at 14:30
  • \$\begingroup\$ I'd recommend investigating the Shunting-yard algorithm. \$\endgroup\$ – Pieter Witvoet Apr 9 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.