Обработка и вычисление математического выражения

[wol4aravio]

Обратная польская нотация не понравилась?

Не не понравилась))) интересовался просто, есть ли более быстрые алгоритмы, это бы очень пригодилось

[Kostia]

Не не понравилась))) интересовался просто, есть ли более быстрые алгоритмы, это бы очень пригодилось

переводится в постфиксную форму, по которой потом строится дерево выражения

Постфиксная форма == обратная польская нотация, разве не?

                           -
                          / \
                         /   \
                        *     E
                       / \
                      /   \
                     /     \
                    /       \
                   +         +
                  / \       / \
                 /   \     /   \
                A     B   C     D

Есть тоже что и AB+CD+*E- (Капитан том 5 :D )
Тут подробный алгоритм: http://algolist.manual.ru/syntax/revpn.php
Правильно его модифицировав можно легко(быстро) считать и значения функций и производные n-го порядка.

[Utkin]

Я уже предлагал не строить никаких деревьев, а разбирать выражение рекурсивно. Я так делал на c#, время работы вполне приличное (в том смысле, что на глаз не видно за какое время считает). Суть там та же, но под другим углом зрения. Я ведь так понимаю Вам нужна интерпретация, а не компиляция. Ваш метод нужен именно для компиляции. При разборе следует использовать одну функцию, которая разбирает выражения вызывая саму себя, до тех пор пока не спустится до примитивов и только тогда возвращает конкретные промежуточные результаты вычислений. Ваш пример:

-x*sin(sqrt(abs(x)))-y*sin(sqrt(abs(y)))

Есть выражение вида a-b, где a=-x*sin(sqrt(abs(x))), b=y*sin(sqrt(abs(y)))
Соответственно для вычисления функция вызывает саму себя для a и для b. В следующем шаге вычисляется a (или b без разницы):
a=a1*b1, где a1=-x, b1=sin(sqrt(abs(x))). Ну и так далее. По сути Вы также спускаетесь по дереву (только немного другого вида), однако само дерево не строится, все промежуточные вычисления сразу же используются для решения операции более высокого уровня.

[Kostia]

Я уже предлагал не строить никаких деревьев, а разбирать выражение рекурсивно. Я так делал на c#, время работы вполне приличное (в том смысле, что на глаз не видно за какое время считает).

Если потребуется многочисленные вычисления значения функции, то лучше хранить выражение уже разобранным в какой либо форме(обратная польская например), а уж разбирать его можно как угодно.
Лично я хранил в обратной польской, а задача стояла в поиске нуля функции, минимума(максимума) разными метода и естественно для некоторых методов требовались первые и вторые производные. Правда я схалявил в плане оптимизации в пользу удобства, как то так:

solve(const char *pol_str, double x, int der = 0);

где der - производная
остальные думаю понятно
Ах, да, у меня все просто было, т.к. функция одной переменной =)

Раз Utkin расписал свой вариант, распишу свой

Преобразовываем -x*sin(sqrt(abs(x)))-y*sin(sqrt(abs(y)))
в $x$#unar_minus#$x$#abs##sqrt##sin##*#$y$#abs##sqrt##sin##-#
В общем все просто, команды заключены в ##, переменные в $$, а константы у меня лично просто болтаются. Опять таки ВНИМАНИЕ, это если вы хотите удобно работать со строкой, более удобная форма хранения это массив объектов(element, varible: public element, operation: public element, const: public element). Далее вы просто бежите по строке(или массиву) слева на право и переменные(значения переменных) и константы толкаете в стек, затем когда встречаете операцию, применяете ее к одному или нескольким элементам стека, т.е. выталкиваете из стека необходимое кол-во значений, работаете с ними и пихаете обратно в стек результат, в конце концов у вас в стеке должен остаться только один элемент, который и является решением.

[Utkin]

Если потребуется многочисленные вычисления значения функции, то лучше хранить выражение уже разобранным в какой либо форме(обратная польская например), а уж разбирать его можно как угодно.

Это будет удобно только если все выражения известны заранее либо если в выражении используется много одинаковых аргументов иначе от оптимизации не будет толку. Но проблема в том, что выражения вводит юзер, а он скорее всего не будет вводить неоптимизированные выражения. То есть вероятность наступления случая когда будет применима оптимизация мала, в тоже время как расходы на ее проведения будут всегда.

ЗЫ.

т.к. функция одной переменной =)

В моих функциях было произвольное число аргументов (я писал язык программирования).