简化二叉表达式树的简洁方法
Clean way to simplify a binary expression tree
我的程序的目标是显示数学表达式的符号导数。在创建表示导数的新树后，很可能我会留下冗余项。
比如下面这棵树就没有简化。
Example of binary expression tree
树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 行长并且还在不断增加，这让我相信一定有更好的方法来做到这一点。
解决此问题的一种典型方法是 visitor pattern。任何时候你需要遍历递归结构，在依赖于节点 "type" 的每个节点应用逻辑，这个模式是一个很好的工具。
对于这个特定问题，特别是在 Java 中，我首先将您的表达式 "abstract syntax tree" 更直接地表示为类型层次结构。
我整理了一个简单的示例，假设您的 AST 处理 +、-、*、/ 以及文字数字和命名变量。我将我的 Visitor 称为 Folder---我们有时将此名称用于类似访问者的名称，以替换 ("fold") 子树。 （思考：编译器中的优化或脱糖过程。）
处理 "I need to sometimes repeat simplification" 的技巧是进行深度优先遍历：在我们简化他们的父级之前，所有子级都得到完全简化。
示例如下（免责声明：我讨厌 Java，所以我不保证这是该语言中最 "idiomatic" 的实现）：
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
我的程序的目标是显示数学表达式的符号导数。在创建表示导数的新树后，很可能我会留下冗余项。
比如下面这棵树就没有简化。
Example of binary expression tree
树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 行长并且还在不断增加，这让我相信一定有更好的方法来做到这一点。
解决此问题的一种典型方法是 visitor pattern。任何时候你需要遍历递归结构，在依赖于节点 "type" 的每个节点应用逻辑，这个模式是一个很好的工具。
对于这个特定问题，特别是在 Java 中，我首先将您的表达式 "abstract syntax tree" 更直接地表示为类型层次结构。
我整理了一个简单的示例，假设您的 AST 处理 +、-、*、/ 以及文字数字和命名变量。我将我的 Visitor 称为 Folder---我们有时将此名称用于类似访问者的名称，以替换 ("fold") 子树。 （思考：编译器中的优化或脱糖过程。）
处理 "I need to sometimes repeat simplification" 的技巧是进行深度优先遍历：在我们简化他们的父级之前，所有子级都得到完全简化。
示例如下（免责声明：我讨厌 Java，所以我不保证这是该语言中最 "idiomatic" 的实现）：
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