8

式ツリーを中置記法に似た形式に変換する作業を行っています。ツリーを評価したり、その操作を実行したりしていません。ツリーには論理演算とリレーショナル演算の両方が含まれているので、翻訳中にインテリジェントな方法で括弧を出力したいと思います。

説明のために、次の不自然な表現を考えてみましょう。

a < x & (a < y | a == c) & a != d

この式で生成された式ツリーを順番に歩くと、次の式が出力されますが、これは正しくありません。

a < x & a < y | a == c & a != d
// equivalent to (a < x & a < y) | (a == c & a != d)

または、順番にトラバーサルを実行することもできますが、バイナリ式の処理の前後に括弧を付けます。これにより、次の正しい式が生成されますが、いくつかの冗長な括弧があります。

(((a < x) & ((a < y) | (a == c))) & (a != d))

最適に括弧で囲まれた式を生成する式ツリー走​​査アルゴリズムはありますか？

ExpressionVisitor参考までに、これは私がツリーを検査するために使用して いるスニペットです。

class MyVisitor : ExpressionVisitor
{
    protected override Expression VisitBinary(BinaryExpression node)
    {
        Console.Write("(");

        Visit(node.Left);
        Console.WriteLine(node.NodeType.ToString());
        Visit(node.Right);

        Console.Write(")");

        return node;
    }

    // VisitConstant, VisitMember, and VisitParameter omitted for brevity.
}
4

2 に答える 2

4

このアルゴリズムを実装するための良い基礎を提供するので、私は弁証法の答えを受け入れました。この回答の唯一の問題は、VisitBinary()メソッドがその親呼び出し元をメソッド引数として認識している必要があることです。これは、これらのメソッドが基本メソッドのオーバーロードであるため、実行可能ではありません。

同様のアルゴリズムを使用する次のソリューションを提供しますが、式ツリーの子ノードの親呼び出しで括弧を発行するためにチェックを適用します。

class MyVisitor : ExpressionVisitor
{
    private readonly IComparer<ExpressionType> m_comparer = new OperatorPrecedenceComparer();

    protected override Expression VisitBinary(BinaryExpression node)
    {
        Visit(node, node.Left);
        Console.Write(node.NodeType.ToString());
        Visit(node, node.Right);

        return node;
    }

    private void Visit(Expression parent, Expression child)
    {
        if (m_comparer.Compare(child.NodeType, parent.NodeType) < 0)
        {
            Console.Write("(");
            base.Visit(child);
            Console.Write(")");
        }
        else
        {
            base.Visit(child);
        }
    }

    // VisitConstant, VisitMember, and VisitParameter omitted for brevity.
}

優先順位比較関数は、演算子の優先順位IComparer<ExpressionType>のC＃ルールを適用するとして実装されます。

class OperatorPrecedenceComparer : Comparer<ExpressionType>
{
    public override int Compare(ExpressionType x, ExpressionType y)
    {
        return Precedence(x).CompareTo(Precedence(y));
    }

    private int Precedence(ExpressionType expressionType)
    {
        switch(expressionType) { /* group expressions and return precedence ordinal * }
    }
}
于 2012-08-24T15:17:27.940 に答える
3

node.NodeTypeがタイプNodeTypeであり、その関数Precedesが存在し、最初のパラメーターが2番目のパラメーターの前にある場合はtrueを返すと仮定して、このようなことを試してください。

protected override Expression Visit(BinaryExpression node, NodeType parentType)
{
    bool useParenthesis = Precedes(parentType, node.NodeType);

    if (useParenthesis)
        Console.Write("(");

    Visit(node.Left, node.NodeType);
    Console.WriteLine(node.NodeType.ToString());
    Visit(node.Right, node.NodeType);

    if (useParenthesis)
        Console.Write(")");

    return node;
}
于 2012-08-21T15:33:12.090 に答える