Программа в делфи, но мне важен сам алгоритм.
Надо подсчитать определённый интеграл заданного функции.
Методы подсчёта определённого интеграла я знаю. Это для случаев, когда функция задана в программном коде. Я понимаю, что методы не изменяются, если функция задана в строке. Но меня интересует вопрос как разложить данную функцию.
В методе требуется находить значения функции при подстановке различных Х.
Я пока придумал 2 варианта разбора выражения:
1) в столке с выражением заменяются все Х на подставляемое значение. Далее идём по строке и в порядке приоритета вычисляем значения малых выражений (умножения двух чисел, сложения, тригонометрические функции от числа и тп)
минус метода в том, что при подсчёте определённого интеграла требуется подставить более 1000 различных Х. Получается более 1000 раз строка вновь и вновь разбирается.
2) Разложить выражение в дерево.
плюс метода в том что разложение происходит один раз – при задания самого выражения и дальше операции происходят непосредственно с ним, а не со строкой
минус – не совсем осмысливаю как это сделать.
к примеру выражение (X*X-5*X)*2
…………………….*
…………………./……\
…………………-……..2
………………/…..\
……………..*……*
……………/..\…../..\
…………..Х…Х…Х…5
как то так.
Может кто-то сможет подкинуть ещё метод или помочь с деревом. Заранее благодарен.
17 апреля 2008 в 15:00
Вот хороший ссайт с софтом
//abc.ru/p/33740/soft
15 апреля 2008 в 9:02
У меня есть своя библиотека, которая парсит любую функциюв виде строки, с любой вложенностью скобок. Но она на С++. Если надо, то в ЛС.
2 апреля 2008 в 0:03
ещё поступило предложение перевести сразу в обратную польскую запись и в неё уже подставлять икс и считать.
1 апреля 2008 в 23:01
Для вычисления интеграла, если мне память не изменяет, функцию придётся вычислять многократно. В этом случае один раз распарсить строку и использовать дерево объектов на подобии предложенного будет эффективнее, чем каждый раз интерпретировать строку.
Я ещё в институте решал такую задачу (тоже для какого-то численного метода). Откомпилированному коду это проигрывало около 20%, кажется.
1 апреля 2008 в 21:02
2 Александр Чигринец
да, вы всё правильно поняли
одного переменного
2 Дима Мироводин
почитал про польскую нотацию
как я понял мы делаем дерево. заменяем икс на подставляемое значение и обходим дерево как обратную польскую запись.
Но в строке можно заменить икс на подставляемое значение и обойти строку а не дерево. значит создание дерева теряет смысл? Или всё же деревья быстрее обойти обратной польской записью нежели строку?
1 апреля 2008 в 18:02
Почти так же просто, но чуть более общо:
class Env {
map<string,double> values;
double get(string name);
void put(string name, double value);
}
(класс Sum)
virtual double eval(Env &env) {
double sum = 0;
for(int i = 0; …) sum += operand.eval(env);
}
(класс Var)
virtual double eval(Env &env) {
return env.get(m_name);
}
1 апреля 2008 в 16:04
Дерево тоже надо грамотно представить.
В свое время я реализовывал поиск экстремума функции (еще во время учебы).
Для каждой поддерживаемой функции был класс, наследуемый от абстрактного базового класса. У абстрактного класса был только один полезный метод (на плюсах выглядит так):
virtual double Calc(double) = 0;
Ну, и все, что требует язык…
В классах в качестве параметров могли быть другие функции. В результате этого дерево представлено вразумительными объектами, которые ничего не парсят, а только считают…
Например (намеренно упрощаю):
class Sum : public IFunc
{
public:
vector<IFunc *> m_operands;
virtual double Calc(double x)
{
double sum = 0;
for (int i = 0, n = m_operands.size(); i < n; ++i)
sum += m_operands[i]->Calc(x);
return sum;
}
};
1 апреля 2008 в 12:01
можно парсить строку методом рекурсивного спуска – проще всего. думаю в сети полно примеров и готовых наработок. если не найдешь напиши в личку – могу выслать работающий парсер на C# для примера
1 апреля 2008 в 11:01
Читать про польскую нотацию
1 апреля 2008 в 9:02
Если я правильно понял, требуется написать парсер. На входе строка из арифмитических действий (+ – * / ^) и простых функций (ln, exp, sin, cos, tg). На выходе – нечто, позволяющее вычислить заданную функцию.
Вопрос: функция, по условию, одного переменного?