Как преобразовать математическое дерево выражений в уменьшенную форму? - PullRequest
Новая
       14

Как преобразовать математическое дерево выражений в уменьшенную форму?

3 голосов
/ 23 марта 2012

Я работаю над некоторым заданием по численному анализу, где я должен оценивать, строить и дифференцировать математические выражения. Среди прочего Я реализовал деревья выражений с Java .

Пока что я могу построить дерево выражений, отобразить его с помощью Latex, оценить его, построить его и получить его производную. Интерфейс, который реализуется составными функциями в дереве, имеет следующие методы: Function[] child();<br> void addChild(Function chld);<br> double evaluate(HashMap subMap);<br> String toLatex();<br> int precedence();<br> 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 way - или, если бы вы взялись за это раньше, ваша помощь будет действительно признательна.

Ответы [ 2 ]

1 голос
/ 23 июля 2012

У меня довольно похожая задача: мне нужно упростить алгебраические выражения, например, (-1)*a + (b - a) + 2*a => b

После небольшого поиска в Google было обнаружено, что Системы компьютерной алгебры должны справляться с такими задачами.

Вот хороший список таких библиотек: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Только что попробовал библиотеку MathEclipse / symja - в ней есть довольно хороший онлайн-оценщик (реализованный с использованием этой библиотеки), который, кажется, делает именно то, что мне нужно, то есть сокращает выражения вроде 0*x => 0, a - b + (-1)*a => -b.

Также вы можете проверить другие библиотеки Java CAS.

Надеюсь, это поможет ...

0 голосов
/ 14 мая 2012

У меня было точно такое же назначение минус латекс. Я полагаю, что вы неправильно подошли к оценке производной.

Это в основном копия из моего задания, ключом здесь является использование какого-либо вида эпсилона и использование других функций, которые у вас уже есть. Дальнейшее объяснение относительно производных разностных коэффициентов можно найти в википедии 

<!-- 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;
    }
}
...