Estrarre tutti i percorsi possibili dall'albero delle espressioni e valutarli per contenere VERO

Questa è una domanda successiva alla mia precedente: link

Breve introduzione:

• regole come stringhe
• combinazioni di logico - e , logico - o , negazione logica e raggruppamento per parentesi di < em> identificatori (ID)

Esempio: "{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})"

Questo viene attualmente valutato in un albero binario di nodi, che assomiglia a questo:

Codicepresodaqui: link

La mia implementazione ( Compilatore online ):

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


namespace Rextester
{
    public class Program
    {
        public static List<int> Rules = new List<int> { 103 , 106 };

        public static void Main( string[] args )
        {
            var ruleStr = CleanupRuleString( "{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})" );
            var inputRules = new List<int> { 103 , 106 };
            var tree = GetTree( ruleStr );
            var resTrue = Evaluate( tree , new List<int> { 100 , 101 } );
            var resFalse = Evaluate( tree , new List<int> { 100 , 103 } );

            Console.WriteLine( "resTrue: {0}" , resTrue );
            Console.WriteLine( "resFalse: {0}" , resFalse );
        }

        public class Expression
        {
            public TokenTypes TokenType = TokenTypes.None;
            public List<Expression> SubExpressions = new List<Expression>();
            public string Literal = null;
        }

        public static Expression GetTree( string ruleStr )
        {
            var tokens = new List<Token>();
            var reader = new StringReader( ruleStr );

            for( var token = new Token( reader ) ; token.TokenType != TokenTypes.None ; token = new Token( reader ) )
            {
                tokens.Add( token );
            }

            tokens = TransformToPolishNotation( tokens );

            var enumerator = tokens.GetEnumerator();

            enumerator.MoveNext();

            return CreateExpressionTree( ref enumerator );
        }

        public static string CleanupRuleString( string ruleStr )
        {
            foreach( var translation in TranslationMap )
            {
                var query = SyntaxMap.Where( x => x.Key == translation.Value ).Select( x => x.Key );

                if( query.Any() )
                    ruleStr = ruleStr.Replace( translation.Key , query.Single().ToString() );
            }

            return new string( ruleStr.ToCharArray().Where( c => !char.IsWhiteSpace( c ) && c != '{' && c != '}' ).ToArray() );
        }

        public static bool Evaluate( Expression expr , List<int> rules )
        {
            if( expr.TokenType == TokenTypes.None )
            {
                return rules.Contains( Convert.ToInt32( expr.Literal ) );
            }
            else if( expr.TokenType == TokenTypes.Not )
            {
                return !Evaluate( expr.SubExpressions.Single() , rules );
            }
            else // binary op
            {
                if( expr.TokenType == TokenTypes.Or )
                    return Evaluate( expr.SubExpressions[ 0 ] , rules ) || Evaluate( expr.SubExpressions[ 1 ] , rules );
                else if( expr.TokenType == TokenTypes.And )
                    return Evaluate( expr.SubExpressions[ 0 ] , rules ) && Evaluate( expr.SubExpressions[ 1 ] , rules );
            }

            throw new ArgumentException();
        }

        public static List<Token> TransformToPolishNotation( List<Token> infixTokenList )
        {
            var outputQueue = new Queue<Token>();
            var stack = new Stack<Token>();

            foreach( var token in infixTokenList )
            {
                switch( token.TokenType )
                {
                    case TokenTypes.Literal:
                    {
                        outputQueue.Enqueue( token );
                    }
                    break;

                    case TokenTypes.Not:
                    case TokenTypes.And:
                    case TokenTypes.Or:
                    case TokenTypes.OpenParen:
                    {
                        stack.Push( token );
                    }
                    break;

                    case TokenTypes.CloseParen:
                    {
                        while( stack.Peek().TokenType != TokenTypes.OpenParen )
                        {
                            outputQueue.Enqueue( stack.Pop() );
                        }

                        stack.Pop();

                        if( stack.Count > 0 && stack.Peek().TokenType == TokenTypes.Not )
                            outputQueue.Enqueue( stack.Pop() );
                    }
                    break;

                    default:
                    break;
                }
            }

            while( stack.Count > 0 )
            {
                outputQueue.Enqueue( stack.Pop() );
            }

            return outputQueue.Reverse().ToList();
        }

        public static Expression CreateExpressionTree( ref List<Token>.Enumerator tokenEnumerator )
        {
            var expression = new Expression();

            if( tokenEnumerator.Current.TokenType == TokenTypes.Literal )
            {
                expression.Literal = tokenEnumerator.Current.Value;

                tokenEnumerator.MoveNext();

                return expression;
            }
            else if( tokenEnumerator.Current.TokenType != TokenTypes.None )
            {
                expression.TokenType = tokenEnumerator.Current.TokenType;

                tokenEnumerator.MoveNext();

                if( expression.TokenType == TokenTypes.Not )
                {
                    expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
                }
                else if( expression.TokenType == TokenTypes.And || expression.TokenType == TokenTypes.Or )
                {
                    expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
                    expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
                }
            }

            return expression;
        }

        public static Dictionary<string,char> TranslationMap = new Dictionary<string,char> {
                { "NOT" , '!' } ,
                { "AND" , '&' } ,
                { "OR" , '|' } ,
            };

        public static Dictionary<char,TokenTypes> SyntaxMap = new Dictionary<char,TokenTypes>() {
                { '(' , TokenTypes.OpenParen } ,
                { ')' , TokenTypes.CloseParen } ,
                { '!' , TokenTypes.Not } ,
                { '&' , TokenTypes.And } ,
                { '|' , TokenTypes.Or } ,
            };

        public enum TokenTypes
        {
            None = -1,
            OpenParen,
            CloseParen,
            And,
            Or,
            Not,
            Literal,
        }

        public class Token
        {
            public TokenTypes TokenType;
            public string Value;

            public Token( StringReader s )
            {
                var charValue = s.Read();

                if( charValue == -1 )
                {
                    this.TokenType = TokenTypes.None;
                    this.Value = string.Empty;

                    return;
                }

                var ch = (char)charValue;

                if( SyntaxMap.ContainsKey( ch ) )
                {
                    this.TokenType = SyntaxMap[ ch ];
                    this.Value = string.Empty;
                }
                else // read literal
                {
                    var sb = new StringBuilder();

                    sb.Append( ch );

                    while( s.Peek() != -1 && !SyntaxMap.ContainsKey( (char)s.Peek() ) )
                    {
                        sb.Append( (char)s.Read() );
                    }

                    this.TokenType = TokenTypes.Literal;
                    this.Value = sb.ToString();
                }
            }
        }
    }
}

Ora ho bisogno di verificare con un dato input di ID che devono essere inclusi e esclusi in modo che l'attuale codepath abbia come risultato TRUE :

input:
[
    103 , 106
]
output:
[
    {
        inclusions: [ 100 , 101 ] ,
        exclusions: [ 106 ]
    } ,
    {
        inclusions: [ 100 , 102 ] ,
        exclusions: [ 106 ]
    } ,
    {
        inclusions: [ 100 , 103 , 104 ] ,
        exclusions: [ 106 ]
    } ,
]

Le mie domande sarebbero:

1. Come faccio ad attraversare l'albero in modo da ottenere tutti i possibili percorsi di codice?
2. Come faccio a tenere traccia di quali ID devono essere incluso / escluso mentre attraversi l'albero?

Ho anche ottenuto questo Q su StackOverflow , ma penso che potrebbe adattarsi meglio qui