在翻译表达式树时如何推断括号的用法?

.net expression-trees inorder parentheses translation

我正在努力将表达式树翻译成类似于中缀表示法的格式;我不是在评估树或执行它的操作。树包含逻辑和关系操作,我想在翻译期间以智能方式发出括号。

为了说明,请考虑以下设计表达:

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.
}

一般承认的答案

尝试这样的事情,假设node.NodeTypeNodeType类型,并且该函数Precedes存在,如果第一个参数在第二个参数之前返回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;
}

热门答案

我接受了Dialecticus答案,因为它为实现这个算法提供了一个很好的基础。这个答案唯一的问题是它需要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 * }
    }
}


许可下: CC-BY-SA with attribution
不隶属于 Stack Overflow
许可下: CC-BY-SA with attribution
不隶属于 Stack Overflow