我正在将表达式树转换为类似于中缀表示法的格式;我不是在评估树或执行它的操作。该树包含逻辑和关系操作,我想在翻译过程中以智能方式发出括号。
为了说明这一点,请考虑以下人为的表达式:
a < x & (a < y | a == c) & a != d
如果我按顺序遍历这个表达式产生的表达式树,那么我会打印出下面的表达式,这是错误的。
a < x & a < y | a == c & a != d
// equivalent to (a < x & a < y) | (a == c & a != d)
或者,我可以再次执行有序遍历,但在处理二进制表达式之前和之后发出括号。这将产生以下正确的表达式,但有几个多余的括号。
(((a < x) & ((a < y) | (a == c))) & (a != d))
是否有一种表达式树遍历算法可以生成最佳括号表达式?
作为引用,这里是
ExpressionVisitor
的片段我正在用来检查树。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 of Dialecticus因为它为实现该算法提供了良好的基础。这个答案的唯一问题是它要求 VisitBinary()
方法知道其父调用者作为方法参数,这是不可行的,因为这些方法是基方法的重载。
我提供了以下解决方案,它使用类似的算法,但应用检查以在父调用中为表达式树的子节点发出括号。
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.
}
优先级比较函数实现为
IComparer<ExpressionType>
,它应用了 operator precedence 的 C# 规则.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 * }
}
}
关于.net - 翻译表达式树时如何推断括号的用法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12057519/