How to make a conclusion about the use of parentheses when translating an expression tree?

Question

I am working on converting an expression tree to a format reminiscent of infix notation; I do not evaluate a tree or perform its operations. The tree contains both logical and relational operations, and I would like that during the translation I would like to generate parentheses.

To illustrate this, consider the following far-fetched expression:

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

If I go through the expression tree created by this expression in order, I will print the next expression, which is incorrect.

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

Alternatively, I can traverse again in order, but emit parentheses before and after processing the binary expression. This will result in the next correct expression, but with a few fallback brackets.

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

Is there an expression tree traversal algorithm that generates expressions with optimal parenthesis?

For reference, here is a snippet of ExpressionVisitor that I use to validate the tree.

 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

Try something similar, assuming that node.NodeType is of type NodeType , and this Precedes function exists and returns true if the first parameter precedes the 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; } 

Answer 2

I accepted Dialecticus answer as it provides a good basis for implementing this algorithm. The only problem with this answer is that it requires the VisitBinary() method to know about its parent caller as an argument to the method, which is not possible because these methods are overloads of the base method.

I provide the following solution, which uses a similar algorithm, but applies verification to emit parentheses in the parent call for child nodes of the expression tree.

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

The priority comparison function is implemented as IComparer<ExpressionType> , which applies the C # operator priority rules.

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