Лучшая структура класса для анализа и оценки логических выражений

c#

209 просмотра

1 ответ

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

Вот мой дополнительный вопрос о том, как это интерпретировать. Он оказался более мощным, чем принятый ответ: извлеките все возможные пути из дерева выражений и оцените их как истинные.


Я получил некоторое логическое выражение для строки во время выполнения:

"100 AND 101"
"102 AND 103 AND 104 AND 105"
"(106 AND 107 AND 108) OR (109 AND 110)"
"111 AND (NOT( 112 AND 113 ))" // NOT is encapsulated in its own group if it is combined

Типы операций:

  • AND для соединения / логического и
  • OR для дизъюнкции / логического или
  • NOT для инверсии / логического.не
  • группировка по скобкам

Операнды - это некоторые идентификаторы, представленные в виде целых чисел.

Я предполагаю, что строка выражения будет:

  • без ошибок
  • нет перемежения дизъюнкций и конъюнкций без группировки (это недействительно: 100 AND 101 OR 102 AND 103)

Мне нужно проанализировать эту строку и проверить ее по списку идентификаторов, если это выражение оценивается как trueили false. Моя текущая структура такова:

public class ExpressionTree
{
    public enum OperationTypes { Not , And , Or }

    public static Dictionary<string , OperationTypes> OperationTypeMap = new Dictionary<string , OperationTypes> {
        { "NOT" , OperationTypes.Not } ,
        { "AND" , OperationTypes.And } ,
        { "OR"  , OperationTypes.Or  } ,
    };

    public class Group
    {
        public OperationTypes OperationType;
        public Group Parent;

        public List<Group> Groups = new List<Group>();
        public List<Identifier> Identifiers = new List<Identifier>();
    }

    public class Identifier
    {
        public OperationTypes OperationType;
        public Group Parent;

        public int Id;
    }

    public Group Root;
}

Однако эта структура не настолько интуитивна, как хотелось бы, и ее оценка также довольно громоздка. Основное внимание должно быть уделено легкому пониманию, производительность не является проблемой.

Существует ли более оптимальная структура классов для такого рода выражений, которую легче интерпретировать?


Вот рабочий пример (могут быть еще ошибки)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;


namespace VisitorPattern
{
    public class Test
    {
        public static void Main2( string[] args )
        {
            var list = new Dictionary<string , List<int>> {
                { "({100} OR {101} OR {102})" ,                                             new List<int> { 100 } } ,
                { "(NOT ({100} OR {101} OR {102}))" ,                                       new List<int> { 0 } } ,
                { "{100} AND {101} AND {102}" ,                                             new List<int> { 100 , 101 , 102 } } ,
                { "{100} OR {101} OR {102}" ,                                               new List<int> { 101 } } ,
                { "NOT ({100})" ,                                                           new List<int> { 0 } } ,
                { "{100} AND (NOT ({101} OR {102} OR {103}))" ,                             new List<int> { 100 , 104 } } ,
                { "({100} AND ({101} OR {102} OR {103})) AND ({104} OR {105} OR {106})" ,   new List<int> { 100 , 103 , 104 } } ,
            };

            foreach( var elem in list )
            {
                var processor = new Processor();
                var ruleVisitor = new RuleVisitor { Rules = elem.Value };
                var node = processor.Parse( elem.Key );
                var result = ruleVisitor.Visit( node , true );

                Debug.Assert( result );
            }
        }
    }

    public interface IVisitor<T>
    {
        T Visit( OrNode node , bool result );
        T Visit( NotNode node , bool result );
        T Visit( AndNode node , bool result );
        T Visit( GroupNode node , bool result );
        T Visit( IdentifierNode node , bool result );
    }

    public class RuleVisitor : IVisitor<bool>
    {
        public List<int> Rules;

        public bool Visit( OrNode node , bool result )
        {
            return node.SubNodes.First().Accept( this , result ) || result;
        }

        public bool Visit( AndNode node , bool result )
        {
            return node.SubNodes.First().Accept( this , result ) && result;
        }

        public bool Visit( NotNode node , bool result )
        {
            return !node.SubNodes.First().Accept( this , result );
        }

        public bool Visit( GroupNode node , bool result )
        {
            return node.SubNodes.Aggregate( result , ( res , child ) => child.Accept( this , res ) );
        }

        public bool Visit( IdentifierNode node , bool result )
        {
            return this.Rules.Contains( node.Identifier );
        }
    }

    #region Node Types

    public abstract class NodeBase
    {
        public List<NodeBase> SubNodes = new List<NodeBase>();

        public abstract T Accept<T>( IVisitor<T> visitor , bool result );
    }

    public class OrNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class NotNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class AndNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class GroupNode : NodeBase
    {
        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    public class IdentifierNode : NodeBase
    {
        public int Identifier;

        public override T Accept<T>( IVisitor<T> visitor , bool result )
        {
            return visitor.Visit( this , result );
        }
    }

    #endregion

    public class Processor
    {
        public enum OperationTypes
        {
            Not,
            And,
            Or,
        }

        public static Dictionary<string , OperationTypes> OperationTypeMap = new Dictionary<string , OperationTypes> {
            { "NOT" , OperationTypes.Not } ,
            { "AND" , OperationTypes.And } ,
            { "OR"  , OperationTypes.Or  } ,
        };

        public GroupNode Parse( string ruleString )
        {
            var index = 0;
            var rootNode = new GroupNode();

            rootNode.SubNodes = this.Parse( ruleString , ref index );

            return rootNode;
        }

        private List<NodeBase> Parse( string ruleString , ref int index )
        {
            var node = default( NodeBase );
            var nodes = new List<NodeBase>();

            for( ; index < ruleString.Length ; index++ )
            {
                var c = ruleString[ index ];

                if( char.IsWhiteSpace( c ) )
                {
                    continue;
                }
                else if( char.IsLetter( c ) )
                {
                    var opType = this.ScanOperationType( ruleString , ref index );

                    if( opType == OperationTypes.And )
                        node = new AndNode();
                    else if( opType == OperationTypes.Or )
                        node = new OrNode();
                    else if( opType == OperationTypes.Not )
                        node = new NotNode();

                    nodes.Add( node );
                }
                else if( c == '(' )
                {
                    if( node == null )
                    {
                        node = new GroupNode();
                        nodes.Add( node );
                    }

                    index++;

                    node.SubNodes.Add( new GroupNode {
                        SubNodes = this.Parse( ruleString , ref index )
                    } );
                }
                else if( c == ')' )
                {
                    index++;

                    break;
                }
                else if( c == '{' )
                {
                    var idNode = new IdentifierNode {
                        Identifier = this.ScanNumber( ruleString , ref index )
                    };

                    if( node == null )
                    {
                        node = idNode;
                        nodes.Add( idNode );
                    }
                    else
                    {
                        node.SubNodes.Add( idNode );
                    }
                }
                else
                {
                    Debug.Fail( "" );
                }
            }

            return nodes;
        }

        private OperationTypes ScanOperationType( string ruleString , ref int index )
        {
            var idx = index;
            var operationType = OperationTypeMap
                .Where( x => ruleString.Length > x.Key.Length + idx - 1 )
                .Where( x => ruleString.Substring( idx , x.Key.Length ) == x.Key )
                .Single();

            index += operationType.Key.Length;

            return operationType.Value;
        }

        private int ScanNumber( string ruleString , ref int index )
        {
            var sb = new StringBuilder();

            for( var c = ruleString[ ++index ] // skip opening brace
               ; index < ruleString.Length
               ; c = ruleString[ ++index ]
               )
            {
                if( char.IsNumber( c ) )
                    sb.Append( c );
                else if( c == '}' )
                    break;
                else
                    Debug.Fail( "" );
            }

            return Convert.ToInt32( sb.ToString() );
        }
    }
}
Автор: nonsensation Источник Размещён: 17.07.2016 01:51

Ответы (1)


3 плюса

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

Решение

Вы можете себе представить, что все ваши лиц ( NOT, OR, AND, ID) происходит от общей абстракции , как Node, что может выполнять некоторые основные операции, например , перечислять Чайлдс и так далее. Затем, если у вас относительно небольшой и фиксированный набор узлов, вы можете применить для вас иерархию классов по шаблону Visitor . Итак, ваш код может выглядеть так:

public interface Visitor<T>
{
    T Visit(OrNode node);
    T Visit(NotNode node);
    T Visit(AndNode node);
    T Visit(IdNode node);
}
public abstract class ANode
{
    public List<ANode> Childs { get; }
    public abstract T Accept<T>(Visitor<T> visitor);
}
public class OrNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}
public class NotNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

public class AndNode : ANode
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

public class IdNode : ANode
{
    public bool Value;
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.Visit(this);
    }
}

И вы можете просто рассчитать значение любого поддерева этого выражения со следующим посетителем:

public class ValueVisitor : Visitor<bool> {
        public bool Visit(OrNode node) {
            return node.Childs.Aggregate(false, (current, child) => current | child.Accept(this));
        }

        public bool Visit(NotNode node) {
            return !node.Childs[0].Accept(this);
        }

        public bool Visit(AndNode node) {
            return node.Childs.Aggregate(true, (current, child) => current & child.Accept(this));
        }

        public bool Visit(IdNode node) {
            return node.Value;
        }
    }

Для простого разбора вашего текста на эту структуру классов вы можете использовать Monadic-Parser-Combinatorsкак Sprache в C #.

Автор: Nikita Sivukhin Размещён: 17.07.2016 02:29
Вопросы из категории :
32x32