乾淨的方法來簡化二進制表達式樹

Question

我的程序的目標是顯示數學表達式的符號派生。創建代表衍生產品的新樹之後，很可能我會留下冗餘條款。

例如，下面的樹不被簡化。

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線，並且不斷增長，這使我相信必須有更好的方法來做到這一點。

Answer 1

這個問題的一個典型方法是visitor pattern。任何時候你需要走一個遞歸結構，在每個節點上應用邏輯，這取決於節點的「類型」，這種模式是一個很好用的工具。

對於這個特定的問題，特別是在Java中，我首先將表達式「抽象語法樹」更直接地表示爲類型層次結構。

我已經把一個簡單的例子，假設你的AST處理+， - ，*，/以及字面數字和命名變量。我打電話給我的Visitor a 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