java - 简化二叉表达式树的简洁方法

Question

我的程序的目标是显示数学表达式的符号导数。在创建表示导数的新树后，很可能会留下多余的术语。

例如，下面的树没有被简化。

Example of binary expression tree

树 0 + 5 * (x * 5) 可以重写为 25 * x

我的程序使用很多很多 if 和 else block 通过检查常量乘以常量等来减少树。然后，它相应地重新排列子树。

这是简化树的递归函数的一小部分:

if(root.getVal().equals("*")) {

        if(root.getLeftChild().getVal().equals("1")) {
            return root.getRightChild();
        }
        else if(root.getRightChild().getVal().equals("1")) {
            return root.getLeftChild();
        }
        else if(root.getLeftChild().getVal().equals("0")) {
            return root.getLeftChild();
        }
        else if(root.getRightChild().getVal().equals("0")) {
            return root.getRightChild();
        }
        else if(root.getLeftChild().getVal().equals("*")) {
            if(root.getRightChild().getType().equals("constant")) {
                if(root.getLeftChild().getLeftChild().getType().equals("constant")) { // Ex: (5*x)*6 ==> 30*x
                    int num1 = Integer.parseInt(root.getRightChild().getVal());
                    int num2 = Integer.parseInt(root.getLeftChild().getLeftChild().getVal());
                    OpNode mult = new OpNode("*");
                    mult.setLeftChild(new ConstNode(String.valueOf(num1 * num2)));
                    mult.setRightChild(root.getLeftChild().getRightChild());

                    return mult;
                }
        ...
        ...
        ...
...

该函数效果很好，除了我需要调用它几次以确保树完全缩减(以防缩减打开另一种缩减可能性)。然而，它有 200 行，而且还在不断增长，这让我相信一定有更好的方法来做到这一点。

Answer 1

解决此问题的一种典型方法是 visitor pattern .任何时候您需要遍历递归结构，在每个节点上应用逻辑，这取决于节点的“类型”，这种模式是一个很好的工具。

对于这个特定问题，特别是在 Java 中，我首先将您的表达式“抽象语法树”更直接地表示为类型层次结构。

我已经整理了一个简单的示例，假设您的 AST 处理 +、-、*、/以及文字数字和命名变量。我将我的 Visitor 称为 Folder——我们有时将此名称用于替换(“折叠”)子树的类似访问者。 (想想:编译器中的优化或脱糖过程。)

处理“我​​有时需要重复简化”的技巧是进行深度优先遍历:在我们简化他们的父级之前，所有子级都得到完全简化。

示例如下(免责声明:我讨厌 Java，所以我不保证这是该语言中最“惯用”的实现):

interface Folder {
    // we could use the name "fold" for all of these, overloading on the
    //   argument type, and the dispatch code in each concrete Expression
    //   class would still do the right thing (selecting an overload using
    //   the type of "this") --- but this is a little easier to follow
    Expression foldBinaryOperation(BinaryOperation expr);
    Expression foldUnaryOperation(UnaryOperation expr);
    Expression foldNumber(Number expr);
    Expression foldVariable(Variable expr);
}

abstract class Expression {
    abstract Expression fold(Folder f);

    // logic to build a readable representation for testing
    abstract String repr();
}

enum BinaryOperator {
    PLUS,
    MINUS,
    MUL,
    DIV,
}

enum UnaryOperator {
    NEGATE,
}

class BinaryOperation extends Expression {
    public BinaryOperation(BinaryOperator operator,
            Expression left, Expression right)
    {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }

    public BinaryOperator operator;
    public Expression left;
    public Expression right;

    public Expression fold(Folder f) {
        return f.foldBinaryOperation(this);
    }

    public String repr() {
        // parens for clarity
        String result = "(" + left.repr();
        switch (operator) {
            case PLUS:
                result += " + ";
                break;
            case MINUS:
                result += " - ";
                break;
            case MUL:
                result += " * ";
                break;
            case DIV:
                result += " / ";
                break;
        }
        result += right.repr() + ")";
        return result;
    }
}

class UnaryOperation extends Expression {
    public UnaryOperation(UnaryOperator operator, Expression operand)
    {
        this.operator = operator;
        this.operand = operand;
    }

    public UnaryOperator operator;
    public Expression operand;

    public Expression fold(Folder f) {
        return f.foldUnaryOperation(this);
    }

    public String repr() {
        String result = "";
        switch (operator) {
            case NEGATE:
                result = "-";
                break;
        }
        result += operand.repr();
        return result;
    }
}

class Number extends Expression {
    public Number(double value)
    {
        this.value = value;
    }

    public double value;

    public Expression fold(Folder f) {
        return f.foldNumber(this);
    }

    public String repr() {
        return Double.toString(value);
    }
}

class Variable extends Expression {
    public Variable(String name)
    {
        this.name = name;
    }

    public String name;

    public Expression fold(Folder f) {
        return f.foldVariable(this);
    }

    public String repr() {
        return name;
    }
}

// a base class providing "standard" traversal logic (we could have
//   made Folder abstract and put these there
class DefaultFolder implements Folder {
    public Expression foldBinaryOperation(BinaryOperation expr) {
        // recurse into both sides of the binary operation
        return new BinaryOperation(
                expr.operator, expr.left.fold(this), expr.right.fold(this));
    }

    public Expression foldUnaryOperation(UnaryOperation expr) {
        // recurse into operand
        return new UnaryOperation(expr.operator, expr.operand.fold(this));
    }

    public Expression foldNumber(Number expr) {
        // numbers are "terminal": no more recursive structure to walk
        return expr;
    }

    public Expression foldVariable(Variable expr) {
        // another non-recursive expression
        return expr;
    }
}

class Simplifier extends DefaultFolder {
    public Expression foldBinaryOperation(BinaryOperation expr) {
        // we want to do a depth-first traversal, ensuring that all
        //   sub-expressions are simplified before their parents...
        // ... so begin by invoking the superclass "default"
        //   traversal logic.
        BinaryOperation folded_expr =
            // this cast is safe because we know the default fold
            //   logic never changes the type of the top-level expression
            (BinaryOperation)super.foldBinaryOperation(expr);

        // now apply our "shallow" simplification logic on the result
        switch (folded_expr.operator) {
            case PLUS:
                // x + 0 => x
                if (folded_expr.right instanceof Number
                        && ((Number)(folded_expr.right)).value == 0)
                    return folded_expr.left;

                // 0 + x => x
                if (folded_expr.left instanceof Number
                        && ((Number)(folded_expr.left)).value == 0)
                    return folded_expr.right;
                break;

            case MINUS:
                // x - 0 => x
                if (folded_expr.right instanceof Number
                        && ((Number)(folded_expr.right)).value == 0)
                    return folded_expr.left;

                // 0 - x => -x
                if (folded_expr.left instanceof Number
                        && ((Number)(folded_expr.left)).value == 0) {
                    // a weird case: we need to construct a UnaryOperator
                    //   representing -right, then simplify it
                    UnaryOperation minus_right = new UnaryOperation(
                            UnaryOperator.NEGATE, folded_expr.right);
                    return foldUnaryOperation(minus_right);
                }
                break;

            case MUL:
                // 1 * x => x
                if (folded_expr.left instanceof Number
                        && ((Number)(folded_expr.left)).value == 1)
                    return folded_expr.right;

            case DIV:
                // x * 1 => x
                // x / 1 => x
                if (folded_expr.right instanceof Number
                        && ((Number)(folded_expr.right)).value == 1)
                    return folded_expr.left;
                break;
        }

        // no rules applied
        return folded_expr;
    }

    public Expression foldUnaryOperation(UnaryOperation expr) {
        // as before, go depth-first:
        UnaryOperation folded_expr =
            // see note in foldBinaryOperation about safety here
            (UnaryOperation)super.foldUnaryOperation(expr);

        switch (folded_expr.operator) {
            case NEGATE:
                // --x => x
                if (folded_expr.operand instanceof UnaryOperation
                        && ((UnaryOperation)folded_expr).operator ==
                           UnaryOperator.NEGATE)
                    return ((UnaryOperation)folded_expr.operand).operand;

                // -(number) => -number
                if (folded_expr.operand instanceof Number)
                    return new Number(-((Number)(folded_expr.operand)).value);
                break;
        }

        // no rules applied
        return folded_expr;
    }

    // we don't need to implement the other two; the inherited defaults are fine
}

public class Simplify {
    public static void main(String[] args) {
        Simplifier simplifier = new Simplifier();

        Expression[] exprs = new Expression[] {
            new BinaryOperation(
                    BinaryOperator.PLUS,
                    new Number(0.0),
                    new Variable("x")
            ),

            new BinaryOperation(
                BinaryOperator.PLUS,
                new Number(17.3),
                new UnaryOperation(
                    UnaryOperator.NEGATE,
                    new UnaryOperation(
                        UnaryOperator.NEGATE,
                        new BinaryOperation(
                            BinaryOperator.DIV,
                            new Number(0.0),
                            new Number(1.0)
                        )
                    )
                )
            ),
        };

        for (Expression expr: exprs) {
            System.out.println("Unsimplified: " + expr.repr());

            Expression simplified = expr.fold(simplifier);
            System.out.println("Simplified: " + simplified.repr());
        }
    }
}

输出:

> java Simplify

Unsimplified: (0.0 + x)
Simplified: x
Unsimplified: (17.3 + --(0.0 / 1.0))
Simplified: 17.3