反復アプローチを使用して、特定の C# 式ツリーの深さを把握する良い方法があるかどうかを把握しようとしています。いくつかの動的な評価に式を使用しますが、まれな (エラー) 状況では、システムが非常に大きい式ツリーを処理してスタックを吹き飛ばそうとすることがあります。ツリーの評価を許可する前に、ツリーの深さを確認する方法を見つけようとしています。
質問する
2252 次
3 に答える
8
式ツリーの問題を具体的に解決しようとするのではなく、動作の悪いツリーを処理するための一般的な手法について説明します。
あなたが提起した問題を解決するための私の一連の記事を読むことから始めたいと思うかもしれません。
これらの記事は、私が JScript に取り組んでいたときに書き戻されたため、例は JScript で書かれています。ただし、これらの概念を C# に適用する方法を理解するのはそれほど難しくありません。
C# で、完全な再帰を行わずに再帰的なデータ構造に対して操作を行う方法のちょっとした例を挙げましょう。次のバイナリ ツリーがあるとします。
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))、 望んだ通りに。
ここで、再帰を 2 回から 1 回に減らすことができることがわかりました。同様の手法を使用して、1 回の再帰から再帰なしにすることができます。このアルゴリズムを完全に反復的にする (つまり、左にも右にも再帰しないようにする) ことは、演習として残されています。
(ちなみに、私はインタビューの質問としてこの問題のバリエーションを尋ねているので、もしあなたが私にインタビューを受けることがあれば、あなたは今、不当な優位性を持っています!)
于 2013-03-29T19:33:19.953 に答える
5
.Net に含まれExpressionVisitorている は再帰的ですが、トリックを使用して反復的なものに変えることができます。
基本的に、ノードのキューを処理しています。キュー内の各ノードに対して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;
}
}
于 2013-03-29T21:31:08.323 に答える
2
再帰を使用してツリーを反復するのではなく、いつでも明示的なメモリ内構造を使用できます。再帰的な動作を厳密に模倣したい場合は、明示的なStack. これは、まだ処理されていないノードに関するすべての情報をヒープに格納しているため、それを使い果たすにはさらに多くの時間がかかります。
これは、ツリーベースの構造を（再帰的ではなく反復的に）トラバースし、そのアイテムの深さとともにすべてのアイテムのフラット化されたシーケンスを返す汎用メソッドです。
public static IEnumerable<Tuple<T, int>> TraverseWithDepth<T>(IEnumerable<T> items
, Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<Tuple<T, int>>(
items.Select(item => Tuple.Create(item, 0)));
while (stack.Any())
{
var next = stack.Pop();
yield return next;
foreach (var child in childSelector(next.Item1))
{
stack.Push(Tuple.Create(child, next.Item2 + 1));
}
}
}
これを使用するには、各要素を直接の子にマップする関数であるルート ノードを渡すだけで、深さの最大値を取得できます。遅延実行のため、トラバース関数によって生成された各アイテムは によってメモリに保持されませんMax。そのため、メモリに保持されるアイテムは、処理されていないが親が処理されているノードのみです。
public static int GetDepth(Expression t)
{
return TraverseWithDepth(new[] { t }, GetDirectChildren)
.Max(pair => pair.Item2);
}
于 2013-03-29T19:46:58.390 に答える