バイナリ式ツリーを簡略化するためのきれいな方法

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

この問題の典型的なアプローチの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