从表达式树中提取所有可能的路径并评估它们是否成立

Question

这是我上一个问题的后续问题：

简介：

规则作为字符串
逻辑与、逻辑或、逻辑非和[的组合=39=]分组通过标识符（ID）

示例："{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})"

这目前被评估为节点的二叉树，看起来像这样：

代码取自此处：How to parse a boolean expression and load it into a class?

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

现在我需要检查给定的 ID 输入，其中哪些需要 included 和 excluded 以便当前代码路径结果 TRUE:

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

我的问题是：

1.如何遍历树以获得所有可能的代码路径？
2. 我如何跟踪哪些 ID 需要 included/excluded?

我正在寻找可能的算法或已经编写的实现，但我更愿意自己编写而不是使用任何类型的表达式库

注意：速度不是问题，只要能正常工作即可，代码要合理易懂

Answer 1

所以您想知道应该添加哪些 ID and/or 从给定的输入中去掉，以便表达式 return 对于该输入为真？

从一个稍微不同的角度来看这个问题可能会有用：可以使这个表达式 return 为真的最小输入是什么？一旦回答了该问题，就可以将您的第一个输入与这些输入进行比较，差异就是您第一个问题的答案。

考虑到表达式的树状结构，递归方法是明智的。对于每个表达式，获取其子表达式（如果有的话）的有效输入应该会给你足够的信息来确定它自己的有效输入：

ID 表达式

ID 表达式始终只有一个有效输入：包含其 ID 的输入。

1  -->  {includes: [1]}

OR 表达式

OR 表达式的子表达式的每个有效输入也是该 OR 表达式本身的有效输入。换句话说，子输入可以连接成一个有效输入列表。

1 OR 2 OR 3:
{includes: [1]}  OR  {includes: [2]}  OR  {includes: [3]}  -->  {includes: [1]}
                                                                {includes: [2]}
                                                                {includes: [3]}
// Each child expression has a single valid input. Together, that's 3 valid inputs.

AND 表达式

AND 表达式的有效输入必须满足每个子表达式的至少一个有效输入，因此结果是所有子表达式的有效输入的组合。

1 AND 2:
{includes: [1]}  AND  {includes: [2]}  -->  {includes: [1, 2]}

(1 OR 2) AND (3 OR 4):
{includes: [1]}  AND  {includes: [3]}  -->  {includes: [1, 3]}
{includes: [2]}       {includes: [4]}       {includes: [1, 4]}
                                            {includes: [2, 3]}
                                            {includes: [2, 4]}
// Each child expression has two valid inputs,
// which can be combined in 4 different ways.

不是表达式

NOT 表达式的有效输入必须违反子表达式的每个有效输入。仅遗漏一个必需的 ID 或包含一个不需要的 ID 就足以违反输入，因此有许多可能的组合。

NOT 1:
NOT {includes: [1]}  -->  {excludes: [1]}

NOT (1 AND 2):
NOT {includes: [1, 2]}  -->  {excludes: [1]}
                             {excludes: [2]}
// There are two minimal inputs that violate the single valid AND input.

NOT (1 OR 2):
NOT {includes: [1]}  -->  {excludes: [1, 2]}
    {includes: [2]}
// There are two inputs, but only one way to violate each,
// so there's only one possible combination.

NOT ((1 OR 2) AND (3 OR 4)):
NOT {include: [1, 3]}  -->  {exclude: [1, 1, 2, 3]}  -->  {exclude: [1, 2, 3]}
    {include: [1, 4]}       {exclude: [1, 1, 2, 4]}       {exclude: [1, 2, 4]}
    {include: [2, 3]}       {exclude: [1, 1, 3, 3]}       {exclude: [1, 3]}
    {include: [3, 4]}       {exclude: [1, 1, 3, 4]}       {exclude: [1, 3, 4]}
                            {exclude: [1, 4, 2, 3]}       {exclude: [1, 2, 3, 4]}
                            {exclude: [1, 4, 2, 4]}       {exclude: [2, 3, 4]}
                            {exclude: [1, 4, 3, 3]}       {exclude: [3, 4]}
                            {exclude: [1, 4, 3, 4]}
                            {exclude: [3, 1, 2, 3]}                |
                            {exclude: [3, 1, 2, 4]}                v
                            {exclude: [3, 1, 3, 3]}
                            {exclude: [3, 1, 3, 4]}       {exclude: [1, 2, 4]}
                            {exclude: [3, 4, 2, 3]}       {exclude: [1, 3]}
                            {exclude: [3, 4, 2, 4]}       {exclude: [3, 4]}
                            {exclude: [3, 4, 3, 3]}
                            {exclude: [3, 4, 3, 4]}
// Each of the 4 AND inputs can be violated in 2 ways, resulting in 2^4 = 16 combinations.
// Removing duplicate IDs and duplicate inputs leaves only 7.
// Furthermore, removing supersets leaves only 3 minimal inputs.

其他说明

如上所示，您需要消除重复输入并删除作为其他超集的输入（例如，{include: [1, 2]} 已经涵盖 {include: [1, 2, 3]}），以便每个方法仅 returns 有效输入的最小集合。

还应删除相互矛盾的输入：

1 AND (NOT 1):
{include: [1], exclude: [1]}  -->  (nothing)
// This expression has no valid inputs.

如果表达式的结果包含两个相反的输入（一个包含某些 ID，另一个不包含相同的 ID），则该表达式始终有效。这可以由不指定 include/exclude ID 的单个输入对象表示。

父表达式需要考虑始终有效（和永不有效）的表达式。 AND、OR 和 NOT 都需要以不同的方式处理边缘情况：

如果其子项之一无效，则 AND 始终无效，但它可以忽略始终有效的子项。
如果其子项之一始终有效，则 OR 始终有效，但它可以忽略从不有效的子项。
不是简单地将始终有效更改为从不有效，反之亦然。

总结

使用递归方法，对不同的表达式类型使用不同的逻辑。
表达式的子表达式的有效输入应该足以确定表达式本身的有效输入。见 1.

从表达式树中提取所有可能的路径并评估它们是否成立

Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

c#

algorithm

binary-tree

decision-tree

graph-algorithm