遍历/转换表达式树

本文关键字：表达式 转换 遍历 | 更新日期: 2023-09-27 17:59:40

我有一个表达式树，需要遍历它并生成特定的字符串。假设我有这棵树

     OR
    /  '
  AND   C
 /   '
A     B

我想把它变成：

(A AND B) OR C

我想使用按顺序遍历，但这并不是我所需要的。

遍历/转换表达式树

最简单的解决方案打印多余的括号：

Visit(node):
  Output "("
  If node.has_left():
    Visit(node.left)
  Output node.label
  If node.has_right():
    Visit(node.right)
  Output ")"

要解决冗余括号问题，请为每个运算符分配左优先级和右优先级，就像在运算符优先级解析中一样，并将父节点的优先级传递给访问。只有当访问节点的优先级低于从父节点传入的优先级时，访问才会输出括号。

abstract class Expression {
}
class Binary extends Expression {
    final String operator;
    final Expression left, right;
    Binary(String operator, Expression left, Expression right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }
    @Override
    public String toString() {
        return String.format("(%s %s %s)", left, operator, right);
    }
}
class Variable extends Expression {
    final String name;
    Variable(String name) {
        this.name = name;
    }
    @Override
    public String toString() {
        return name;
    }
}
@Test
public void testExpression() {
    Expression e = new Binary("OR", new Binary("AND", new Variable("A"), new Variable("B")), new Variable("C"));
    System.out.println(e);
    // -> ((A AND B) OR C)
}
相关文章：