Извлеките все возможные пути из дерева выражений и оцените их как истинные

c# algorithm binary-tree graph-algorithm decision-tree

318 просмотра

1 ответ

1398 Репутация автора

Это следующий вопрос из моего предыдущего: Лучшая структура класса для анализа и оценки логических выражений.


Краткое введение:

  • правила как строки
  • комбинации логических-и , логических или , логических-отрицаний и группировка с помощью скобок из идентификаторов (идентификаторы)

Пример: "{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})"

Это в настоящее время оценивается в двоичное дерево узлов, которое выглядит следующим образом: график

Код взят отсюда: как разобрать логическое выражение и загрузить его в класс?

Моя реализация ( онлайн-компилятор ):

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

Теперь мне нужно проверить с помощью заданного ввода идентификаторов, какие из них нужно включить и исключить, чтобы текущий путь к коду приводил к TRUE :

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

Мои вопросы будут:

1. Как мне пройти по дереву, чтобы получить все возможные пути кода?
2. Как я могу отслеживать, какие идентификаторы должны быть включены / исключены ?

Я ищу возможные алгоритмы или уже написанные реализации, но я бы предпочел написать это сам, чем использовать какую-либо библиотеку выражений


Примечание: скорость не имеет значения, она просто должна работать, а код должен быть разумным и понятным

Автор: nonsensation Источник Размещён: 17.07.2016 09:36

Ответы (1)


2 плюса

2267 Репутация автора

Решение

Итак, вы хотите знать, какие идентификаторы вы должны добавить и / или убрать из заданного ввода, чтобы выражение возвращало true для этого ввода?

Вероятно, полезно взглянуть на это с несколько иной точки зрения: какие минимальные входные данные могут сделать это выражение верным? Как только на этот вопрос ответят, ваш первый вклад можно сравнить с этими входами, и различия являются ответом на ваш первый вопрос.

Рекурсивный подход был бы разумен, учитывая древовидную структуру ваших выражений. Для каждого выражения получение действительных входных данных для его дочерних выражений (если оно есть) должно дать вам достаточную информацию для определения его собственных допустимых входных данных:

Идентификационные выражения

У выражений идентификаторов всегда есть один действительный вход: тот, который включает их идентификатор.

1  -->  {includes: [1]}

ИЛИ выражения

Каждый допустимый ввод для дочернего выражения выражения 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 должен удовлетворять как минимум одному допустимому входу каждого дочернего выражения, поэтому результаты представляют собой комбинацию действительного ввода всех дочерних выражений.

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 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.

Если результаты для выражения содержат два противоположных ввода (один включает в себя определенные идентификаторы, а другой исключает одинаковые идентификаторы), тогда это выражение всегда допустимо. Это может быть представлено одним входным объектом, который не указывает идентификаторы включения / исключения.

Всегда допустимые (и никогда не действительные) выражения должны учитываться родительскими выражениями. И, ИЛИ, и НЕ каждый должен обрабатывать этот крайний случай по-своему:

  • AND всегда недействителен, если один из его дочерних элементов недопустим, но он может игнорировать всегда допустимый дочерний элемент.
  • ИЛИ всегда допустимо, если один из его потомков всегда действителен, но он может игнорировать недействительные потомки.
  • НЕ просто изменяет всегда действительный на никогда недействительный и наоборот.

Резюме

  1. Используйте рекурсивный подход с различной логикой для разных типов выражений.
  2. Допустимых входных данных для дочернего выражения (выражений) выражения должно быть достаточно для определения допустимых входных данных для самого выражения. Смотрите 1.
Автор: Pieter Witvoet Размещён: 19.07.2016 09:59
Вопросы из категории :
32x32