简化二叉表达式树的干净方法

Question

简化二叉表达式树的干净方法

3

我的程序目标是展示数学表达式的符号导数。创建一个代表导数的新树后，很可能会留下冗余项。

例如，以下树未简化。二叉表达式树示例树 0 + 5 * (x * 5) 可以重写为 25 * x 我的程序使用许多，许多if和else块通过检查常数乘以常数等来减少树。然后，它相应地重新排列子树。

这是我递归函数的一小部分，用于简化树：

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行代码并且还在不断增长，这让我相信一定有更好的方法来解决这个问题。

- defoification

1

“有一个更好的方法来做这件事”…是的，编写一个解析器，你的生活将变得更加轻松。 - Tim Biegeleisen

2

@TimBiegeleisen OP已经将表达式解析为表达式树，但现在想应用“简化”规则，例如合并常量。 - Andreas

@Andreas 谢谢，我现在明白了。我可能最初不会使用树。也许您可以回答如何简化树的问题。 - Tim Biegeleisen

特别是在面向对象的语言中，人们倾向于使用访问者模式（https://en.wikipedia.org/wiki/Visitor_pattern）来实现这一点。我会考虑为每个“终端节点”的“种类”创建不同的（子）类型（例如，运算符、数字...）。然后，将遍历树的递归逻辑抽象出来到访问者中，并创建一个访问者子类型，例如用`a`替换每个`BinaryOperator(+, a, 0)`。 - Derrick Turk

@DerrickTurk 非常感谢。这种设计方法很有道理，我一定会使用它。但是，这只是将相同的逻辑放入不同的类中，还是您可以想到任何更简单的逻辑呢？ - defoification

@defoification：与您在此处展示的组织方式相比，逻辑上的主要变化将是使用深度优先递归遍历：这是如何使用单个递归“折叠”处理“保持减少几次”的问题的。为表达式树构建类型层次结构也极大地简化了事情（这通常是OO语言中实现访问者模式的方式；在具有代数类型和模式匹配的语言中，它甚至更简单）。也许如果明天早上没有人留下更详细的答案，我会发布一个简单的例子。 - Derrick Turk

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Derrick Turk · Accepted Answer

这个问题的一个典型方法是访问者模式。每当您需要遍历一个递归结构，在每个节点应用依赖于节点“类型”的逻辑时，这种模式是一个很好的工具。

针对这个特定的问题，特别是在Java中，我会开始更直接地表示您的表达式“抽象语法树”作为一种类型层次结构。

我已经提供了一个简单的示例，假设您的AST处理+、-、*、/以及文字数字和命名变量。我将我的访问者称为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