I am working on translating an expression tree to a format that resembles infix notation; I am not evaluating the tree or executing its operations. The tree contains both logical and relational operations, and I would like to emit parentheses in an intelligent manner during the translation.

To illustrate, consider the following contrived expression:

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

If I walk the expression tree produced by this expression in-order, then I will print out the following 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 again perform an in-order traversal but emit parentheses before and after processing a binary expression. This will produce the following correct expression, but with several redundant parentheses.

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

Is there an expression tree traversal algorithm that produces optimally-parenthesized expressions?

For reference, here is a snippet of the `ExpressionVisitor`

I am using to inspect 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.
}
```

Try something like this, assuming that `node.NodeType`

is of type `NodeType`

, and that function `Precedes`

exists and returns true if 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;
}
```

I've accepted the answer of Dialecticus as it provides a good basis for implementing this algorithm. The only issue with this answer is that it requires that the `VisitBinary()`

method know about its parent caller as a method argument, which is not feasible since these methods are overloads of a base method.

I provide the following solution, which uses a similar algorithm, but applies the check to emit parentheses in the parent call for the 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 precedence comparison function is implemented as an `IComparer<ExpressionType>`

, which applies the C# rules of operator precedence.

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

Licensed under: CC-BY-SA with attribution

Not affiliated with Stack Overflow