AJ *_*son 7 c# lambda expression
我试图弄清楚是否有一种很好的方法来使用迭代方法计算出特定C#表达式树的深度.我们使用表达式进行一些动态评估,在罕见(错误)条件下,系统可以尝试处理一个如此大的表达式树,它会吹掉堆栈.我试图找出一种方法来检查树的深度,然后才允许评估树.
而不是试图专门解决表达式树的问题,让我为您描述一些处理表现不佳的树的一般技巧.
您可能希望从阅读我关于解决您所提出的问题的一系列文章开始:如何在不使用递归的情况下确定树的深度？
我在编写JScript时写了这些文章,所以这些例子都是用JScript编写的.但是,要想将这些概念应用于C#并不是很难.
让我在C#中给你一个小玩具示例,说明如何在递归数据结构上进行操作而不进行完全递归.假设我们有以下二叉树:(假设WOLOG表示二叉树节点是零或两个子节点,从不是一个.)
class Node
{
public Node Left { get; private set; }
public Node Right { get; private set; }
public string Value { get; private set; }
public Node(string value) : this(null, null, value) {}
public Node(Node left, Node right, string value)
{
this.Left = left;
this.Right = right;
this.Value = value;
}
}
...
Node n1 = new Node("1");
Node n2 = new Node("2");
Node n3 = new Node("3");
Node n3 = new Node("4");
Node n5 = new Node("5");
Node p1 = new Node(n1, n2, "+");
Node p2 = new Node(p1, n3, "*");
Node p3 = new Node(n4, n5, "+");
Node p4 = new Node(p2, p3, "-");
所以我们有树p4:
-
/ \
* +
/ \ / \
+ 3 4 5
/ \
1 2
我们希望打印出p4作为带括号的表达式
(((1+2)*3)-(4+5))
递归解决方案很简单:
static void RecursiveToString(Node node, StringBuilder sb)
{
// Again, assuming either zero or two children.
if (node.Left != null)
sb.Append(node.Value);
else
{
sb.Append("(");
RecursiveToString(node.Left, sb);
sb.Append(node.Value);
RecursiveToString(node.Right, sb);
sb.Append(")");
}
}
现在假设我们知道树在左边可能"深",但在右边"浅".我们可以消除左边的递归吗？
static void RightRecursiveToString(Node node, StringBuilder sb)
{
// Again, assuming either zero or two children.
var stack = new Stack<Node>();
stack.Push(node);
while(stack.Peek().Left != null)
{
sb.Append("(");
stack.Push(stack.Peek().Left);
}
while(stack.Count != 0)
{
Node current = stack.Pop();
sb.Append(current.Value);
if (current.Right != null)
RightRecursiveToString(current.Right, sb);
sb.Append(")");
}
}
}
当然,只有右侧的递送版本更难以阅读并且更难以推理,但它并没有破坏堆栈.
让我们来看看我们的例子吧.
push p4
push p2
output (
push p1
output (
push n1
output (
loop condition is met
pop n1
output 1
go back to the top of the loop
pop p1
output +
recurse on n2 -- this outputs 2
output )
go back to the top of the loop
pop p2
output *
recurse on n3 -- this outputs 3
output )
go back to the top of the loop
pop p4
output -
recurse on p3
push p3
push n4
output (
loop condition is met
pop n4
output 4
go back to the top of the loop
pop p3
output +
recurse on n5 -- this outputs 5
output )
loop condition is not met; return.
output )
loop condition is not met, return.
我们输出了什么？(((1+2)*3)-(4+5)), 如预期的.
所以你在这里看到我可以从两次递归到一次递归.我们可以使用类似的技术从一次递归到一次递归.使这个算法完全迭代 - 以便它既不在左边也不在右边 - 都是一个练习.
(顺便说一句:我问这个问题的变种是一个面试问题,所以如果你接受我的采访,你现在有一个不公平的优势!)
该ExpressionVisitor包含在.NET是递归的，但使用了一招，你可以把它变成一个迭代。
基本上，您正在处理节点队列。对于队列中的每个节点，使用base.Visit()访问其所有子节点，然后将这些子节点添加到队列中，而不是立即递归处理它们。
这样，您不必编写特定于每个Expression子类型的代码，但您还可以解决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;
}
}