Wie schließe ich die Verwendung von Klammern beim Übersetzen eines Ausdrucksbaums ab?

.net expression-trees inorder parentheses translation

Frage

Ich arbeite an der Übersetzung eines Ausdrucksbaums in ein Format, das der Infix-Notation ähnelt. Ich werte den Baum nicht aus oder führe seine Operationen nicht aus. Der Baum enthält sowohl logische als auch relationale Operationen, und ich möchte während der Übersetzung intelligente Klammern ausgeben.

Betrachten Sie zur Veranschaulichung den folgenden konstruierten Ausdruck:

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

Wenn ich den von diesem Ausdruck erzeugten Ausdrucksbaum in der richtigen Reihenfolge durchführe, dann drucke ich den folgenden Ausdruck aus, der falsch ist.

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

Alternativ kann ich erneut eine In-Order-Traversierung durchführen, aber vor und nach der Verarbeitung eines binären Ausdrucks Klammern ausgeben. Dies erzeugt den folgenden korrekten Ausdruck, jedoch mit mehreren überflüssigen Klammern.

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

Gibt es einen Traversal-Algorithmus für den Ausdrucksbaum, der in optimaler Weise Ausdrücke in Klammern erzeugt?

Zur Referenz: Hier ist ein Ausschnitt des ExpressionVisitor ich den Baum begutachte.

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

Akzeptierte Antwort

Versuchen Sie etwas wie node.NodeType , vorausgesetzt, dass node.NodeType vom Typ NodeType ist und die Funktion Precedes existiert und true zurückgibt, wenn der erste Parameter vor dem zweiten steht.

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

Beliebte Antwort

Ich habe die Antwort von Dialecticus akzeptiert, da sie eine gute Grundlage für die Implementierung dieses Algorithmus bietet. Das einzige Problem bei dieser Antwort ist, dass die VisitBinary() -Methode über ihren übergeordneten Aufrufer als Methodenargument informiert werden muss, was nicht durchführbar ist, da diese Methoden Überladungen einer Basismethode sind.

Ich stelle die folgende Lösung bereit, die einen ähnlichen Algorithmus verwendet, die Überprüfung jedoch anwendet, um Klammern im übergeordneten Aufruf für die untergeordneten Knoten des Ausdrucksbaums auszugeben.

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

Die IComparer<ExpressionType> ist als IComparer<ExpressionType> implementiert, der die C # -Regeln der Operatorpriorität anwendet.

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


Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum