如何迭代确定C#表达式树的深度? [英] How to determine the depth of a C# Expression Tree Iterativly?

问题描述

我正在尝试找出是否存在一种使用迭代方法找出特定C#表达式树深度的好方法.我们使用表达式进行一些动态评估，并且在极少数(错误)情况下，系统可以尝试处理太大的表达式树，以至于耗尽整个堆栈.我正在尝试找出一种方法，以便在评估树之前先检查树的深度.

I am trying to figure out if there is a good way to figure out the depth of a particular C# Expression Tree using an iterative approach. We use expressions for some dynamic evaluation and under rare (error) conditions, the system can try to process an Expression Tree that is so large that it blows out the stack. I'm trying to figure out a way to check the depth of the tree prior to allowing the tree to be evaluated.

推荐答案

.Net中包含的ExpressionVisitor是递归的，但是使用一种技巧，您可以将其转换为迭代的.

The ExpressionVisitor that is included in .Net is recursive, but using a trick, you can turn it into an iterative one.

基本上，您正在处理节点队列.对于队列中的每个节点，使用base.Visit()访问其所有子节点，然后将这些子节点添加到队列中，而不是立即递归处理它们.

Basically, you're processing a queue of nodes. For each node in the queue, use base.Visit() to visit all of its children, but then add those children into the queue instead of recursively processing them right away.

这样，您不必编写特定于每个Expression子类型的代码，但是您还可以解决ExpressionVisitor的递归性质.

This way, you don't have to write code specific to each Expression subtype, but you also work around the recursive nature of ExpressionVisitor.

class DepthVisitor : ExpressionVisitor
{
    private readonly Queue<Tuple<Expression, int>> m_queue =
        new Queue<Tuple<Expression, int>>();
    private bool m_canRecurse;
    private int m_depth;

    public int MeasureDepth(Expression expression)
    {
        m_queue.Enqueue(Tuple.Create(expression, 1));

        int maxDepth = 0;

        while (m_queue.Count > 0)
        {
            var tuple = m_queue.Dequeue();
            m_depth = tuple.Item2;

            if (m_depth > maxDepth)
                maxDepth = m_depth;

            m_canRecurse = true;

            Visit(tuple.Item1);
        }

        return maxDepth;
    }

    public override Expression Visit(Expression node)
    {
        if (m_canRecurse)
        {
            m_canRecurse = false;
            base.Visit(node);
        }
        else
            m_queue.Enqueue(Tuple.Create(node, m_depth + 1));

        return node;
    }
}

这篇关于如何迭代确定C#表达式树的深度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！