This is a follow-up question of my previous one: https://stackoverflow.com/questions/38421950/better-class-structure-for-logical-expression-parsing-and-evaluation
Brief introduction:
- rules as strings
- combinations of logical-and, logical-or, logical-negation and grouping by parenthesis of identifiers (ID's)
Example: "{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})"
This gets currently evaluated into a binary-tree of nodes, that looks like this:
Code taken from here: https://stackoverflow.com/questions/17568067/how-to-parse-a-boolean-expression-and-load-it-into-a-class
My implementation (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();
}
}
}
}
}
Now I need to check by a given input of ID's which of them need to be included and excluded so that the current codepath results in TRUE:
input:
[
103 , 106
]
output:
[
{
inclusions: [ 100 , 101 ] ,
exclusions: [ 106 ]
} ,
{
inclusions: [ 100 , 102 ] ,
exclusions: [ 106 ]
} ,
{
inclusions: [ 100 , 103 , 104 ] ,
exclusions: [ 106 ]
} ,
]
My questions would be:
1. How do I traverse the tree so that I get all possible code-paths?
2. How do I keep track which ID's need to be included/excluded while traversing the tree?
I also got this Q on StackOverflow, but I think it may fit in better in here
