Comment déduire l'utilisation de parenthèses lors de la traduction d'un arbre d'expression?

.net expression-trees inorder parentheses translation

Question

Je travaille sur la traduction d'un arbre d'expression dans un format qui ressemble à la notation infixe; Je ne suis pas en train d'évaluer l'arbre ou d'exécuter ses opérations. L'arbre contient à la fois des opérations logiques et relationnelles, et j'aimerais émettre des parenthèses de manière intelligente lors de la traduction.

Pour illustrer, considérons l'expression artificielle suivante:

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

Si je parcours l'arborescence d'expression produite par cette expression dans l'ordre, je vais imprimer l'expression suivante, qui est incorrecte.

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

Alternativement, je peux à nouveau effectuer une traversée dans l’ordre mais émettre des parenthèses avant et après le traitement d’une expression binaire. Cela produira l'expression correcte suivante, mais avec plusieurs parenthèses redondantes.

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

Existe-t-il un algorithme de traversée de l'arborescence des expressions qui génère des expressions entre parenthèses optimales?

Pour référence, voici un extrait de l' ExpressionVisitor j'utilise pour inspecter l'arbre.

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

Réponse acceptée

Essayez quelque chose comme ceci, en supposant que node.NodeType est de type NodeType et que la fonction Precedes existe et renvoie true si le premier paramètre précède le second.

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

Réponse populaire

J'ai accepté la réponse de Dialecticus car elle fournit une bonne base pour implémenter cet algorithme. Le seul problème avec cette réponse est qu'elle nécessite que la méthode VisitBinary() connaisse son appelant parent en tant qu'argument de méthode, ce qui n'est pas réalisable car ces méthodes sont des surcharges d'une méthode de base.

Je propose la solution suivante, qui utilise un algorithme similaire, mais applique le contrôle pour émettre des parenthèses dans l'appel parent pour les nœuds enfants de l'arborescence des expressions.

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 fonction de comparaison de précédence est implémentée en tant que IComparer<ExpressionType> , qui applique les règles C # de priorité des opérateurs .

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


Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi