Better Class-Structure for logical expression parsing and evaluation

Question

Here is my follow-up question on how to interpret this. It turned out to be more powerfull than the accepted answer: Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

---

I got some logical expression fro a string at runtime:

"100 AND 101"
"102 AND 103 AND 104 AND 105"
"(106 AND 107 AND 108) OR (109 AND 110)"
"111 AND (NOT( 112 AND 113 ))" // NOT is encapsulated in its own group if it is combined

Operation types are:

• AND for conjunction/logical-and
• OR for disjunction/logical-or
• NOT for inversion/logical.not
• grouping by parenthesis

The operands are some Id's represented as integers.

I'm assuming the expression-string to be:

• free of errors
• no interleaving of disjunctions and conjunctions without grouping (this is invalid: 100 AND 101 OR 102 AND 103)

I need to parse this string and check it against a list of ID's if this expression evaluates to true or false. My current structure is this:

public class ExpressionTree
{
    public enum OperationTypes { Not , And , Or }

    public static Dictionary<string , OperationTypes> OperationTypeMap = new Dictionary<string , OperationTypes> {
        { "NOT" , OperationTypes.Not } ,
        { "AND" , OperationTypes.And } ,
        { "OR"  , OperationTypes.Or  } ,
    };

    public class Group
    {
        public OperationTypes OperationType;
        public Group Parent;

        public List<Group> Groups = new List<Group>();
        public List<Identifier> Identifiers = new List<Identifier>();
    }

    public class Identifier
    {
        public OperationTypes OperationType;
        public Group Parent;

        public int Id;
    }

    public Group Root;
}

However this structure isn't as intuitive as I'd like it to be and its evaluation is also abit cumbersome. The main focus should be easy understandability, perfomance isnt a concern.

Is there a more optimal class structure for this kind of expressions that is more easier to interpret?

---

Here is a working example (there may be still bugs)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;


namespace VisitorPattern
{
    public class Test
    {
        public static void Main2( string[] args )
        {
            var list = new Dictionary<string , List<int>> {
                { "({100} OR {101} OR {102})" ,                                             new List<int> { 100 } } ,
                { "(NOT ({100} OR {101} OR {102}))" ,                                       new List<int> { 0 } } ,
                { "{100} AND {101} AND {102}" ,                                             new List<int> { 100 , 101 , 102 } } ,
                { "{100} OR {101} OR {102}" ,                                               new List<int> { 101 } } ,
                { "NOT ({100})" ,                                                           new List<int> { 0 } } ,
                { "{100} AND (NOT ({101} OR {102} OR {103}))" ,                             new List<int> { 100 , 104 } } ,
                { "({100} AND ({101} OR {102} OR {103})) AND ({104} OR {105} OR {106})" ,   new List<int> { 100 , 103 , 104 } } ,
            };

            foreach( var elem in list )
            {
                var processor = new Processor();
                var ruleVisitor = new RuleVisitor { Rules = elem.Value };
                var node = processor.Parse( elem.Key );
                var result = ruleVisitor.Visit( node , true );

                Debug.Assert( result );
            }
        }
    }

    public interface IVisitor<T>
    {
        T Visit( OrNode node , bool result );
        T Visit( NotNode node , bool result );
        T Visit( AndNode node , bool result );
        T Visit( GroupNode node , bool result );
        T Visit( IdentifierNode node , bool result );
    }

    public class RuleVisitor : IVisitor<bool>
    {
        public List<int> Rules;

        public bool Visit( OrNode node , bool result )
        {
            return node.SubNodes.First().Accept( this , result ) || result;
        }

        public bool Visit( AndNode node , bool result )
        {
            return node.SubNodes.First().Accept( this , result ) && result;
        }

        public bool Visit( NotNode node , bool result )
        {
            return !node.SubNodes.First().Accept( this , result );
        }

        public bool Visit( GroupNode node , bool result )
        {
            return node.SubNodes.Aggregate( result , ( res , child ) => child.Accept( this , res ) );
        }

        public bool Visit( IdentifierNode node , bool result )
        {
            return this.Rules.Contains( node.Identifier );
        }
    }

    #region Node Types

    public abstract class NodeBase
    {
        public List<NodeBase> SubNodes = new List<NodeBase>();

        public abstract T Accept<T>( IVisitor<T> visitor , bool result );
    }

    public class OrNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class NotNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class AndNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class GroupNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class IdentifierNode : NodeBase
    {
        public int Identifier;

        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    #endregion

    public class Processor
    {
        public enum OperationTypes
        {
            Not,
            And,
            Or,
        }

        public static Dictionary<string , OperationTypes> OperationTypeMap = new Dictionary<string , OperationTypes> {
            { "NOT" , OperationTypes.Not } ,
            { "AND" , OperationTypes.And } ,
            { "OR"  , OperationTypes.Or  } ,
        };

        public GroupNode Parse( string ruleString )
        {
            var index = 0;
            var rootNode = new GroupNode();

            rootNode.SubNodes = this.Parse( ruleString , ref index );

            return rootNode;
        }

        private List<NodeBase> Parse( string ruleString , ref int index )
        {
            var node = default( NodeBase );
            var nodes = new List<NodeBase>();

            for( ; index < ruleString.Length ; index++ )
            {
                var c = ruleString[ index ];

                if( char.IsWhiteSpace( c ) )
                {
                    continue;
                }
                else if( char.IsLetter( c ) )
                {
                    var opType = this.ScanOperationType( ruleString , ref index );

                    if( opType == OperationTypes.And )
                        node = new AndNode();
                    else if( opType == OperationTypes.Or )
                        node = new OrNode();
                    else if( opType == OperationTypes.Not )
                        node = new NotNode();

                    nodes.Add( node );
                }
                else if( c == '(' )
                {
                    if( node == null )
                    {
                        node = new GroupNode();
                        nodes.Add( node );
                    }

                    index++;

                    node.SubNodes.Add( new GroupNode {
                        SubNodes = this.Parse( ruleString , ref index )
                    } );
                }
                else if( c == ')' )
                {
                    index++;

                    break;
                }
                else if( c == '{' )
                {
                    var idNode = new IdentifierNode {
                        Identifier = this.ScanNumber( ruleString , ref index )
                    };

                    if( node == null )
                    {
                        node = idNode;
                        nodes.Add( idNode );
                    }
                    else
                    {
                        node.SubNodes.Add( idNode );
                    }
                }
                else
                {
                    Debug.Fail( "" );
                }
            }

            return nodes;
        }

        private OperationTypes ScanOperationType( string ruleString , ref int index )
        {
            var idx = index;
            var operationType = OperationTypeMap
                .Where( x => ruleString.Length > x.Key.Length + idx - 1 )
                .Where( x => ruleString.Substring( idx , x.Key.Length ) == x.Key )
                .Single();

            index += operationType.Key.Length;

            return operationType.Value;
        }

        private int ScanNumber( string ruleString , ref int index )
        {
            var sb = new StringBuilder();

            for( var c = ruleString[ ++index ] // skip opening brace
               ; index < ruleString.Length
               ; c = ruleString[ ++index ]
               )
            {
                if( char.IsNumber( c ) )
                    sb.Append( c );
                else if( c == '}' )
                    break;
                else
                    Debug.Fail( "" );
            }

            return Convert.ToInt32( sb.ToString() );
        }
    }
}

Answer 1

You can imagine, that all of your entities(NOT, OR, AND, ID) derived from common abstraction like Node, that can perform some basic operations, for example enumerate childs and so on. Then, if you have relatively small and fixed set of nodes, you can apply for you hierarchy of classes pattern Visitor. So, your code may be looks like this:

public interface Visitor<T>
{
    T Visit(OrNode node);
    T Visit(NotNode node);
    T Visit(AndNode node);
    T Visit(IdNode node);
}
public abstract class ANode
{
    public List<ANode> Childs { get; }
    public abstract T Accept<T>(Visitor<T> visitor);
}
public class OrNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}
public class NotNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

public class AndNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

public class IdNode : ANode
{
    public bool Value;
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

And you can simply calculate value of any subtree of this expression with the next visitor:

public class ValueVisitor : Visitor<bool> {
        public bool Visit(OrNode node) {
            return node.Childs.Aggregate(false, (current, child) => current | child.Accept(this));
        }

        public bool Visit(NotNode node) {
            return !node.Childs[0].Accept(this);
        }

        public bool Visit(AndNode node) {
            return node.Childs.Aggregate(true, (current, child) => current & child.Accept(this));
        }

        public bool Visit(IdNode node) {
            return node.Value;
        }
    }

For easily parsing your text to this class-structure you can use Monadic-Parser-Combinators like Sprache in C#.