这是我上一个问题的后续问题:Better Class-Structure for logical expression parsing and evaluation
简介:
- 规则作为字符串
- 逻辑与、逻辑或、逻辑非和分组的组合 em>标识符(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?
我的实现(Online Compiler):
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 输入来检查哪些 ID 需要包含和排除，以便当前的代码路径结果为TRUE:
input:
[
103 , 106
]
output:
[
{
inclusions: [ 100 , 101 ] ,
exclusions: [ 106 ]
} ,
{
inclusions: [ 100 , 102 ] ,
exclusions: [ 106 ]
} ,
{
inclusions: [ 100 , 103 , 104 ] ,
exclusions: [ 106 ]
} ,
]
我的问题是:
1.如何遍历树以获得所有可能的代码路径？
2.如何跟踪哪些 ID 需要包含/排除？
我正在寻找可能的算法或已经编写的实现，但我更愿意自己编写而不是使用任何类型的表达式库
注意:速度不是问题，只需要在其中工作即可，代码要合理易懂
最佳答案
所以您想知道您应该添加和/或从给定输入中删除哪些 ID，以便表达式为该输入返回 true？
从一个稍微不同的角度来看这个问题可能很有用:可以使这个表达式返回 true 的最小输入是什么？一旦回答了该问题，就可以将您的第一个输入与这些输入进行比较，差异就是您第一个问题的答案。
考虑到表达式的树状结构，递归方法是明智的。对于每个表达式，获取其子表达式(如果有的话)的有效输入应该会给你足够的信息来确定它自己的有效输入:
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 表达式
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]})，这样每个方法只返回最小的有效输入集。
矛盾的输入也应该被删除:
1 AND (NOT 1):
{include: [1], exclude: [1]} --> (nothing)
// This expression has no valid inputs.
如果表达式的结果包含两个相反的输入(一个包含某些 ID，另一个不包含相同的 ID)，则该表达式始终有效。这可以由不指定包含/排除 ID 的单个输入对象表示。
父表达式需要考虑始终有效(和永不有效)的表达式。 AND、OR 和 NOT 都需要以不同的方式处理边缘情况:
- 如果其子项之一无效，则 AND 始终无效，但它可以忽略始终有效的子项。
- 如果其子项之一始终有效，则 OR 始终有效，但它可以忽略永远无效的子项。
- 不是简单地将始终有效更改为从不有效，反之亦然。
总结
- 使用递归方法，针对不同的表达式类型使用不同的逻辑。
- 表达式子表达式的有效输入应该足以确定表达式本身的有效输入。见 1。
关于c# - 从表达式树中提取所有可能的路径并评估它们是否成立，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38426175/