如何转换的表达式目录树时，我推断括号的使用情况如何？(How do I infer the usag

我正在翻译的表达式树类似于中间符号的格式; 我不评价树或执行其业务。 在树中的逻辑和关系操作，我想在翻译过程中发出的括号以智能的方式。

为了说明，考虑以下表达式做作：

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

Answer 1:

尝试这样的事情，假设node.NodeType是类型的NodeType ，并且该功能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;
}

Answer 2:

我已经接受了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 * }
    }
}

文章来源: How do I infer the usage of parentheses when translating an expression tree?