수식 표현 트리를 축소 된 형태로 변환하는 방법은 무엇입니까?

Question

수학적 표현을 평가하고, 음모를 구분하고, 차별화해야하는 수치 해석 할당 작업을하고 있습니다. 다른 것들 중에. Java으로 표현식 트리를 구현했습니다.

지금까지 표현 트리를 만들고 라텍스로 표시하고 평가하고 플롯하고 파생물을 얻을 수 있습니다. 트리의 복합 함수에 의해 구현 된 인터페이스는 다음과 같습니다. Function[] child();
void addChild(Function chld);
double evaluate(HashMap subMap);
String toLatex();
int precedence();
Function derivative();
내가 구현 한 코드는 Constant, Variable, Add, Subtract, Multiply, Divide, Power, Sine, Cosine, Ln입니다. 나는 몇 가지 기본적인 기능을 구별 할 때
지금, 나는 비 감소 형태로 그것을 얻을 :
파생 상품이 가장 일반적인 방식으로 구현되기 때문이다 d/dx(x^2) ===> x^2 * (1 * 2/x + 0 * ln(x))
.

내가 생각한 해결책은 f의 자식이 주어진 각 노드 f의 구성에서 자식을 재귀 적으로 줄이고 순진한 재구성을 수행하는 것입니다. 그러한 재건 후에, 아이들은 f과 관련하여 "함께"감소합니다. 0 * X, 나무가 같아야 식 주어진 예
:

* 표시 노드의 건설

 
    * 
/\ 
0 x 

이 경우 자식 중 하나가 제로 상수는 * 노드 제로 일정하게 . 물론 아이들을 버리게됩니다.

 
    0 

등 다른 모든 승산의 경우에도 마찬가지입니다. 이것은 필자를 대신하여 많은 분석이 필요하며 모든 경우를 다루지는 않습니다 - 곱셈 만이 필요한 기능이 아니라는 것을 명심하십시오.

주어진 작업 : 표현 트리를 사용하면 기본 감소를 어떻게 할 수 있습니까?이 문제에 대한 해결책을 제시하는 링크 나 논문을 참조 할 수 있다면 (바람직하게는 우아한 OO 방식으로) 또는 이전에 태클 한 적이 있다면 이 실제로이 될 것입니다.

Answer 1

에서 찾을 수 있습니다 내가 예를 들어, 대수식을 단순화 할 필요가 (-1)*a + (b - a) + 2*a => b

약간의 인터넷 검색 결과, Computer algebra systems이 이러한 작업을 처리해야한다는 것을 알게되었습니다.

여기에 같은 라이브러리의 좋은 목록이있다 : http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

은 MathEclipse/symja 라이브러리를 시도 - 내가 즉 필요 0*x => 0 같은 표현을 줄이기 바로 일을 할 것 같다 (이 라이브러리를 사용하여 구현) 아주 좋은 온라인 평가를 가지고 , a - b + (-1)*a => -b.

기타 Java CAS 라이브러리를 확인할 수도 있습니다.

희망 ...

Answer 2

정확히 동일한 임무에서 라텍스를 뺀 것이 있습니다. 나는 당신이 파생 상품 평가에 올바르게 접근하지 않았다고 믿습니다.

이것은 기본적으로 내 과제에서 복사 한 붙여 넣기입니다. 여기서 핵심은 어떤 종류의 엡실론을 사용하고 이미 가지고있는 다른 기능을 사용하는 것입니다. 유도 difference quotients에 대한 추가 설명은 내가 매우 유사 작업이 위키 피 디아

<!-- language: lang-java --> 
/** 
* 
This class represents a RealFunction that is the derivative 
of the other real function. 

*/ 

public class DerivativeFunction implements RealFunction{ 
     private RealFunction toDiff; 
    private double _epsilon; 
    private static final int TWO = 2; 
    /** 
    * Constructs a new DerivativeFunction object. 
Numerical computation of the derivative is performed at each point, 
epsilon is used to approximate the 
lim (f(x+t/2) - f(x-t/2))/t. 

    * @param f the function whose derivative is to be approximated 
    * @param epsilon the value used instead of t-->0 
     in the derivative formula. 
    */ 

    public DerivativeFunction(RealFunction f, double epsilon) { 
     this.toDiff = f; 
     this._epsilon = epsilon; 

    } 
    /** 
    * returns the value of f'(x). 

    * @param x the x value given. 

    * @return the value f'(x) of this function i.e (f(x+epsilon/2)-f(x - epsilon/2))/epsilon. 
*/ 

    public double valueAt(double x) { 
     double reminder = this._epsilon/TWO; 
     return (this.toDiff.valueAt(x + reminder) - this.toDiff.valueAt(x - reminder))/this._epsilon; 
    } 
}