0

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: graph

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

  • C# already has first-class expression trees, so unless this is merely a learning exercise you're probably better off going that route. – Robert Harvey Jul 18 '16 at 20:16
1

You need an expression evaluator, as an abstract syntax tree interpreter.

What an interpreter does is: start with some known state, e.g. variables, (blank) outputs, etc.. Then it execute statements to update that state.

To execute expression statements, you might use a recursive expression evaluator, which would do something like this:

  • for a constant node, fetch the constant value and return it as the value of the evaluation
  • for a variable node, fetch the value of the variable and return it as the value of the evaluation
  • for a binary operator, evaluate left child (hold result), then evaluate right child, then based on the operator type appropriately combine the left-result with the right-result. Then return that value as value of the evaluation.

In your system a simple value has a type of: a list of inclusions maybe together with a list of exclusions (depending on your language semantics). Each operator manipulates these lists. The NOT operator, for example, might filter the current inclusion list, and depending on your semantics, also add something to the exclusion list.

Larger interpreters (and their associated languages) will have a notion of multiple types, such as single boolean, string, integer, list, etc... but you might get away with having just one type.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.