¿Cómo puedo inferir el uso de paréntesis al traducir un árbol de expresiones?

.net expression-trees inorder parentheses translation

Pregunta

Estoy trabajando en la traducción de un árbol de expresiones a un formato que se asemeja a la notación de infijo; No estoy evaluando el árbol ni ejecutando sus operaciones. El árbol contiene operaciones lógicas y relacionales, y me gustaría emitir paréntesis de manera inteligente durante la traducción.

Para ilustrar, considere la siguiente expresión artificial:

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

Si recorro en orden el árbol de expresiones producido por esta expresión, imprimiré la siguiente expresión, que es incorrecta.

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

Alternativamente, puedo volver a realizar un recorrido en orden pero emitir paréntesis antes y después de procesar una expresión binaria. Esto producirá la siguiente expresión correcta, pero con varios paréntesis redundantes.

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

¿Existe un algoritmo transversal de árbol de expresiones que produzca expresiones de paréntesis óptimas?

Para referencia, aquí hay un fragmento del ExpressionVisitor que estoy usando para inspeccionar el árbol.

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

Respuesta aceptada

Intente algo como esto, asumiendo que node.NodeType es de tipo NodeType , y que la función Precedes existe y devuelve true si el primer parámetro precede al segundo.

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

Respuesta popular

He aceptado la respuesta de Dialecticus ya que proporciona una buena base para implementar este algoritmo. El único problema con esta respuesta es que requiere que el método VisitBinary() conozca a su interlocutor principal como un argumento de método, lo cual no es factible ya que estos métodos son sobrecargas de un método base.

Proporciono la siguiente solución, que utiliza un algoritmo similar, pero aplica la verificación para emitir paréntesis en la llamada principal para los nodos secundarios del árbol de expresiones.

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

La función de comparación de precedencia se implementa como un IComparer<ExpressionType> , que aplica las reglas C # de la precedencia del operador .

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


Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow
Licencia bajo: CC-BY-SA with attribution
No afiliado con Stack Overflow