이진 표현 트리를 단순화하는 명확한 방법

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을 Folder이라고했는데, 때로는이 이름을 하위 트리를 대체하는 ("fold") 방문객 용으로 사용합니다. (생각해보기 : 컴파일러에서 최적화 또는 탈 설탕 패스)

"때때로 간소화를 반복해야합니다"라는 처리 방법은 깊이 우선 탐색을 수행하는 것의 트릭입니다. 부모를 단순화하기 전에 모든 어린이가 완전히 단순화됩니다. 여기

은 예입니다 (면책 조항 : 나는 자바를 싫어, 그래서이 가장 '관용적'언어로 구현 한 것입니다 약속하지 않음) :

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