論理式の解析と評価のためのより良いクラス構造

Question

これを解釈する方法に関する私の後続の質問があります。それは受け入れ答えよりも強力であることが判明：Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

---

私は、実行時に文字列のあちこちにいくつかの論理式を得た：

"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 disjuncオペランドがいくつかのIDが整数として表現されている括弧

によってグループ化

反転/ logical.notため NOT

ン/論理または

。

私はあることを表現文字列を想定していないよ：

• エラー
• の自由選言と接続詞のないインターリーブをグループ化することなく、（これは無効です：100 AND 101 OR 102 AND 103）

私が必要この式がtrueまたはfalseと評価された場合、この文字列を解析してIDのリストと照合します。 私の現在の構造はこれです：

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

しかし、この構造は、私はそれがしたいほど直感的ではなく、その評価もabitは面倒です。 主な焦点は理解しやすいものでなければならず、性能は重要ではありません。

この種の表現には、解釈がより簡単なクラス構造が最適ですか？ここ

---

は実施例である（まだバグがあるかもしれません）

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

Answer 1

あなたのようなあなたのエンティティのすべて（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; 
     } 
    } 

簡単にこのクラス - にあなたのテキストを解析するためにあなたはSpracheのようなMonadic-Parser-CombinatorsをC＃で使うことができます。