Comment évaluer l'arbre d'expression avec des opérateurs logiques en C#

Question

J'ai une structure arborescente avec des nœuds feuilles contenant des expressions, qui sont affirmées être Vrai ou Faux, connectées par des conditions logiques (ET/OU). Je recherche un algorithme/une solution pour évaluer l'arbre par Depth-first-search, basé sur des opérateurs logiques Si le nœud parent est un ET alors aucune autre traversée à un frère n'est requise si le nœud courant est évalué comme faux . (aussi si le noeud courant est VRAI alors pas de frère à visiter si le noeud parent est un OU) - Cela permettrait d'optimiser l'évaluation. Je suis juste curieux de savoir s'il y a déjà une solution/code plutôt que de la réinventer .

public class TreeNode<T> 
{ 
    private readonly T _value; 
    private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>(); 

    public TreeNode(T value) 
    { 
     _value = value; 
    } 

    public TreeNode<T> this[int i] 
    { 
     get { return _children[i]; } 
    } 

    public TreeNode<T> Parent { get; private set; } 

    public T Value { get { return _value; } } 

    public ReadOnlyCollection<TreeNode<T>> Children 
    { 
     get { return _children.AsReadOnly(); } 
    } 

    public TreeNode<T> AddChild(T value) 
    { 
     var node = new TreeNode<T>(value) {Parent = this}; 
     _children.Add(node); 
     return node; 
    } 

    public TreeNode<T>[] AddChildren(params T[] values) 
    { 
     return values.Select(AddChild).ToArray(); 
    } 

    public bool RemoveChild(TreeNode<T> node) 
    { 
     return _children.Remove(node); 
    } 

    public void Traverse(Action<T> action) 
    { 
     action(Value); 
     foreach (var child in _children) 
      child.Traverse(action); 
    } 

    public IEnumerable<T> Flatten() 
    { 
     return new[] {Value}.Union(_children.SelectMany(x => x.Flatten())); 
    } 
} 

Remarque: Je pourrais facilement faire un BFS récursives en C#, mais celui-ci plus difficile trouvé Image of sample tree structure

Answer 1

Faites une traversal récursive de l'arbre. Vous collectez le résultat de l'évaluation de chaque noeud enfant, puis appliquez votre opération logique et renvoyez le résultat. La logique de base serait comme ci-dessous.

Le code est un pseudocode semblable à C#. À partir du code que vous avez posté, je ne vois pas clairement comment vous différenciez les nœuds opérateurs (ET et OR) des nœuds ayant des valeurs True et False. Mais vous devriez être capable d'utiliser cet algorithme de base avec quelques modifications pour s'adapter à votre code.

bool EvaluateNode(TreeNode node) 
{ 
    // if it's a child node, return its value 
    if (node has no children) 
    { 
     return node._value; 
    } 

    switch node.Operator 
    { 
     case operator.AND: 
      // for AND, we can shortcut the evaluation if any child 
      // returns false. 
      for each child 
      { 
       if (EvaluateNode(child) == false) 
        return false; 
      } 
      // all children returned true, so it's true 
      return true; 

     case operator.OR: 
      // for OR, we can shortcut the evaluation if any child 
      // returns true. 
      for each child 
      { 
       if (EvaluateNode(child) == true) 
        return true; 
      } 
      // none were true, so must be false 
      return false; 
     default: 
      // Unknown operator. Some error. 
      break; 
    } 

} 

Si vous ne voulez pas faire d'évaluation de raccourci, cela fonctionne toujours. Vous venez de changer légèrement vos boucles. Par exemple, le cas et serait:

bool result = true; 
for each child 
{ 
    result = result & EvaluateNode(child); 
} 
return result; 

Et le cas OU serait:

bool result = false; 
for each child 
{ 
    result = result | EvaluateNode(child); 
} 
return result;