Суть задачи. Идет разбор математического выражения, состоящего из математических функций и арифметических дейтсвий.
Предположим, что мы имеем стек операций, который надо вычислить. К примеру:
Функция: f(x)=(sin(x+2)-exp(2*x))*3
При разборе получаем следующий стек вида (даю не точный идпри работе програмы, а лишь схему (все данные стека - строки, работа с которыми ведется через регулярныет выражения и последующим рекурсивным вычислением)):
0 - х+2
1 - sin([0])
2 - 2*x
3 - exp([2])
4 - ([1]+[3])
5 - [4]*3

Так вот, вопрос в чем. Нашу ф(х) надо вычислить многократно (к примеру от 0 до 1 с шагом 0.01). Сделать это - не проблема, но, мне не хочется при каждом новом вычислении значении функции, производить рекурсивный разбор (точнее сбор) кусочков функции и их вычисление.

Можно ли как-то сделать стек вычислений, т.е. один раз показать программе, что sin - это sin из math.h и потом к нему и обращаться, просто передавая новое значение аргумента?

Работаю на C++, Qt4, Linux.

Я делал на первом курсе лабу, только там были ф-ии вложенные, небыло операторов - что-то вроде sin(tg(sqrt(x))), и по этой беде строился график. Для этого создавался список - односвязный - примерно такого вида:



затем, эта хрень вызывалась рекурсивно



Это сообщение отредактировал(а) Lazin - 23.8.2007, 14:15

Lazin, это-то все мне понятно. Сам процесс вычисления - проблем не вызывает, тут вопрос в оптимальном решении при большом кол-ве вызовов этих самых вычислений.

Что-бы разобрать сложное выражение наверное нужно использовать деревья а не списки

Добавлено через 5 минут и 58 секунд
Так-или иначе всё равно придется создавать структуру данных отражающую процесс вычислений, хотя возможно получится использовать итерацию для обхода, а это немного быстрее.

Mal Hack, я тут подумал, подумал... может, помогут лямбда-функции? то есть при первом разборе при рекурсивном проходе мы "накапливаем" эту самую функцию как boost::function1<double, double>, в конце разбора сохраняем ее как



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

Lazin, я же вроде написал, что проблема НЕ В РАЗБОРЕ И НЕ В АЛГОРИТМЕ !!!!

JackYF, а можно что-ть более развернуто на тему лямбда функции почитать? Не имел с этим дело и мало представляю себе суть.

 Есть такое предложение:
 Выражение парситься в ПОЛИЗ. и потом преобразуется во внутреннее представление.
 Ну например:
 sin(exp(x+2)) : ->  x 2 + exp sin 
 во внутреннем представление: 10 байт на число (double) и флажок вызова функции. если есть флажок - то содержимое стека трактуется как адрес этой функции

в стеке 

адрес функции возвращающей в стек x
2.0
адрес функции производящей сложение
адрес функции считающей экспоненту
адрес функции считающей синус

получаем что то типа виртуальной машины небольшой)))))
... дальше дело техники 


PS если используешь .NET - советую динамические сборки опробывать. Генерируешь в IL код метода. JITer его один раз скомпилирует. Дальше летать будет)))

ЗЗЫ
 вот ссылка на компилятор выражения в байт-код (правда на дельфи и какой то уцербный но может пригодиться) 


Это сообщение отредактировал(а) Sartorius - 23.8.2007, 15:17

2JackYF Разве шаблоны не на этапе компиляции обрабатываются, boost::lamda не исключение.

Sartorius, как я понимаю, все равно, придется парсить функцию при каждом новом значении аргумента.
А мне надо, отпарсить один раз, сделать что-то вроде макроса (запомнить последовательность действий), а затем вызывать эту последовательность действий для нового значения X.

.NET я не использую.

Mal Hack, нет. Функция парситься один раз. А вместо х - в стек записывается адрес функции , возвращающей x. или вообще можно ввести три типа элементов стека - константы, функции и переменные. 
 С константами все понятно. 
 Если следующим из стека достается адрес функции - то она вызвается  и ей передается адрес вершины стека, так , что б она могла брать аргументы и класть туда возвращаемое значение. 
 Если достается переменная - то в стек возвращается ее значение.

PS чего - то подзабыл как с польской записью работать поэтому путанно объяснил наверно. 
 Стоит различать стек - хранилище данных. И цепочку команд.
 Сейчас все покорректней сформулирую:
 sin(15 * x + exp(5))  - > в польской записи   15 x * 5 exp + sin  - эту цепочку переведем во внутреннее представление

 номер инструкции   тип (два бита или байт)                  значение
[0]   константа                                                15
[1]   переменная                                              адрес х
[2]   функция                                                   умножение
[3]   константа                                                 5
[4]   функция                                                    exp
[5]   функция                                                    сложение
[6]   функция                                                    sin


теперь когда эта небольшая программа заработает на нашей "виртуальной стековой машине" произойдет следующее
[0] встретили константу в цепочке  - кладем значение на стек
[1] встретили переменную - читаем ее адрес и кладем на стек
[2] встретили функцию - читаем ее адрес вызываем и передаем ей стек
...
уф... вроде теперь нормально объяснил





Это сообщение отредактировал(а) Sartorius - 23.8.2007, 15:44

Гм...

При парсинге можно собирать указатели на необходимые функции и потом пользоваться ими.

1. Переводим выражение в обратную польскую запись
например (2 * x + 3) * 6 = 2 x * 3 + 6 *
2. Составляем связный список узлов элементарных операций
а) Каждый узел имеет структуру

функция вычисления по узлам выглядит следующим образом


Это сообщение отредактировал(а) MAKCim - 23.8.2007, 15:51

Sartorius, так так так... Мысля вроде бы появилась...
А вот как мне быть, если: 

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

Mal Hack,  наверно если хочешь сохранить в таком виде вычисление математики - то в цепочке команд функцию надо задавать индексом mathFncType type а не адресом, передавать в качестве  паоамеьов - два значения с вершины стека. и после вызова evalMathFnc класть ее возврат в стек. только есть одна засада - неизвестно сколько значений 1 или 2 ей реально понадобилось для вычислений. Так что в этом случае придется возвращать не double а структуру


и после возврата корректно очищать сте

Я вот думаю, что тут проще вместо адреса на функцию сделать поле со значением типа mathFncType и в случае, если очередная запись в стеке этого типа, вызывать функию evalMathFnc и передавать ей аргумент и этот тип...

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