Qt и разбор математических выражений Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Переключить на: Древовидный Переключить на: Стандартный Линейный

[AD]

Может кто-нибудь подскажет, есть ли готовый, разборщик мат. выражений (в смысле, можно взять исходный код и вставить к себе в программу)? Нет желания изобретать велосипед, уверен, что это уже реализовывали. Хотелось бы увидеть такого рода код. Буду благодарен за любые ссылки.

Да, забыл указать: в результате хотелось бы иметь один из следующих вариантов:
На входе строка с математическим выражением:
На выходе

- массив строковых выражений, содержащий либо операцию, либо операнд
- массив структур такого рода
[1 ОПЕРАНД ОПЕРАЦИЯ 2 ОПЕРАНД]
- что-то наподобие первых двух....

[fsMark]

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

[trdm]

Как насчет бизончика или QLalr или как там оно называется?

[AD]

Как насчет бизончика или QLalr или как там оно называется?

На мой взгляд для такой задачи использовать бизон, як, лекс, флекс и прочее как-то не очень! Да и потом килобайты кода раскапывать! Фу....

[trdm]

Ну, это смотря с какой целью тебе разборшик нужен.

кстати чета: http://labs.trolltech.com/blogs/category/l...ompilers/qlalr/
не фига не открывается (((

[AD]

Ну, это смотря с какой целью тебе разборшик нужен.

Да в том-то и дело, что цели по-мелочам и использовать для этих мелочей такие крутые средства - роскошь!

[trdm]

не, я всетаки добрался
svn://labs.trolltech.com/svn/compilers/qlalr
Хоть эта ссылка работает. Буду посмотреть

[AD]

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

Сообщение отредактировал AD - 25.9.2008, 10:43

[Tonal]

А чё ты с этими "массивчиками" делать собираешся?
Может проще QScript использовать?

[AD]

Это уже не как массив. Сразу вычисляю. Короче, могу сказать для чего мне это надо! Я выкладывал проект, так там были нарисованы такие красявые графики зависимости одних параметров от времени или от расстояния. Значения параметров брались из лог-файлов. Но хотелось бы еще видеть графики зависимости параметров, которые вычисляются из полученных.
Формулы, как правило, довольно простые. А сложные формулы не пишутся, а пишутся имена функций, которые их вычисляют (таких очень немного, пока 4, но будет не более 8-10).
Вот пример формул, которые уже умею разбирать, практически:

diff_Hgnss_Hbaro    = (Hgnss - Hbaro) * raspd + Hbaro * raspd
diff_test111        = v_spd * Hra
Hmax            = GetHMax(lat / 30, lon + 10)
Haccuratly        = GetHAccuratly(lat, lon)
diff_mslAlt_Hmax    = msl_alt - Hmax
diff_mslAlt_Hacc    = msl_alt - Haccuratly

[Litkevich Yuriy]

Может проще QScript использовать?

Присоеденяюсь (хоть сам и не пользовал).

[AD]

А чё ты с этими "массивчиками" делать собираешся?
Может проще QScript использовать?

Возможно! Но в Qt 4.3.1 я нашел только QtScript module или же QScriptContext! Да и... уже ведь реализовано (практически)!

[Tonal]

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

[AD]

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

Что-то я в ассистенте примеров использования не увидел. Можете дать ссылки на примерчики? Заранее спасибо! Может среди самих qt-шных примеров есть пример использования QScriptContext, QScriptEngine?

[Litkevich Yuriy]

целый каталог %QTDIR%\examples\script

[AD]

целый каталог %QTDIR%\examples\script

Ага, спасибо! На будущее буду иметь в виду.

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

[ViGOur]

Выкладывай, заодно и покритикуем!

[AD]

Выкладывай, заодно и покритикуем!

Ну.... адекватно только.

А то критика типа ЛАЖА, ФИГНЯ или же типа такой, что надо было пользоваться разборщиками или QScript, а не изобретать велосипед, и т.п. не принимается! критика на счет не использования QtScript - поздно узнал. На счет разборщиков - уже объяснял.

source

/// Структура, хранящая операции, которые выполняются над параметрами
struct COMPUTE
{
public:
    std::string op;                    ///< операция, которую выполняют над аргументами
    double arg1, arg2;                ///< аргументы оператора
    int arg1_index, arg2_index;        ///< индексы, по которым располагаются в векторе аргументы

public:
    COMPUTE(): op(""), arg1(0.0), arg2(0.0), arg1_index(0), arg2_index(0) {}
    COMPUTE(const COMPUTE& o): op(o.op), arg1(o.arg1), arg2(o.arg2), arg1_index(o.arg1_index),
                               arg2_index(o.arg2_index) {}
    COMPUTE(const char* o, double ar1, double ar2): op(0), arg1(ar1), arg2(ar2), arg1_index(0), arg2_index(0) {}
    bool operator==(const COMPUTE& o) { return op == o.op && arg1 == o.arg1 && arg2 == o.arg2 &&
                                        arg1_index == o.arg1_index && arg2_index == o.arg2_index; }
    const COMPUTE& operator=(const COMPUTE& o)
    { op = o.op; arg1 = o.arg1; arg2 = o.arg2; arg1_index = o.arg1_index; arg2_index = o.arg2_index; return *this; }
    virtual double GetValue();
};

/// Расширенная структура для выполнения более сложных операций
struct EXCOMPUTE: public COMPUTE
{
public:
    int arg_count;                    ///< количество аргументов функции
    double *arg1, *arg2;            ///< указатели на аргументы функции

public:
    EXCOMPUTE(int count = 4);
    EXCOMPUTE(const EXCOMPUTE& o);
    EXCOMPUTE(const COMPUTE& o): arg1(0), arg2(0) { op = o.op; arg1_index = o.arg1_index; arg2_index = o.arg2_index;
                        COMPUTE::arg1 = 0.0; COMPUTE::arg2 = 0.0; }
    ~EXCOMPUTE() { delete[] arg1; delete[] arg2; }
    bool operator==(const EXCOMPUTE& o);
    const EXCOMPUTE& operator=(const EXCOMPUTE& o);
    const EXCOMPUTE& operator=(const COMPUTE& o) { op = o.op; COMPUTE::arg1 = 0.0; COMPUTE::arg2 = 0.0; return *this; }
    double GetValue();
};

/// Класс для вычисления параметра
class ElemFormul
{
protected:
    QStringList formul_list;                ///< список простых формул, которые следует вычислять

public:
    ElemFormul(QStringList e): formul_list(e) {}
    ~ElemFormul() {}
    COMPUTE* calculateFormul(LOGRECORD* record, std::vector<ParamDescr*>* vec);
    COMPUTE* calc(LOGRECORD* record, std::vector<ParamDescr*>* vec, QStringList& ls, QList<double>& rs_vl);
    int argumentIndex(std::vector<ParamDescr*>* vec, QString arg);
};

/// Класс для описания вычисляемых параметров
class CompParamDescr: public ParamDescr
{
protected:
    COMPUTE* op;                            ///< указатель на операции для вычисления параметров
    std::string expression;                    ///< выражение, которое следует вычислить для получения параметра
    QStringList formul_list;                ///< список простых формул, которые следует вычислять
    unsigned int index;                        ///< индекс данного элемента

private:
    void buildString(QString& expr, QStringList& ls);
    QString remove_symbols(const char* op, QString expr);
    void determOperation(QString& expr, QStringList& ls, const QRegExp& exp, const QRegExp& d_exp);
    void determDifficultOp(QString& expr, QStringList& ls, const QRegExp& df_exp);

public:
    CompParamDescr(): expression(""), index(-1), op(0) {}
    COMPUTE* opVec() const { return op; }
    void opVec(const COMPUTE* v);
    std::string Expr() const { return expression; }
    void Expr(const std::string e) { expression = e; }
    PARAMVALUE GetValue(Uint word);
    QStringList formulList() { return formul_list; }
    void formuList(const QStringList& l) { formul_list = l; }
    void addFormul();
};

/// Добавление в список простейшей вычислимой формулы
void CompParamDescr::addFormul()
{
    QRegExp exp(BASE_OPERATIONS);
    QString str_expr = expression.c_str(), e = "";
    for(int matched = 0, ind = 0; (matched = exp.indexIn(str_expr, matched)) != -1;
        ++ind, matched += exp.matchedLength())
    {
        string operation = exp.capturedTexts().at(0).toStdString();
        if(operation == ",") { matched += exp.matchedLength(); ++ind; continue; }
        if(operation.size() > 2)
        {
            e = remove_symbols(operation.c_str(), str_expr);
            break;
        }
        else e = str_expr.simplified();
    }
    buildString(e, formul_list);
}

/// Формирование простейшей разбираемой строки
void CompParamDescr::buildString(QString& expr, QStringList& ls)
{
    const char *simple_op_low_priority = "[+-]", *simple_op_high_priority = "[*/]";
    QRegExp exp_low(simple_op_low_priority), exp_high(simple_op_high_priority), exp(BASE_OPERATIONS);
    QRegExp exp_diff("gethmax|gethaccuratly");
    string hs = expr.toStdString();
    if(expr.find(")") != -1 && expr.find("(") != -1)
    {
        QString ex = expr.section(")", 0, 0).simplified(), reserve = expr.section(")", 0, 0).simplified() + ")";
        ex = ex.section("(", 1, 1).simplified();
        buildString(ex, ls);
        expr = expr.replace(reserve, "#val");
        if(!expr.isEmpty()) buildString(expr, ls);
    }
    else if(expr.find(exp_diff) != -1) determDifficultOp(expr, ls, exp_diff);
    else if(expr.find(exp_high) != -1) determOperation(expr, ls, exp_high, exp_low);
    else if(expr.find(exp_low) != -1) determOperation(expr, ls, exp_low, exp_high);
}

/// Определение выполняемой операции и помощь в формировании строки
void CompParamDescr::determOperation(QString& expr, QStringList& ls, const QRegExp& exp, const QRegExp& d_exp)
{
    QString left_expr = "", right_expr = "";
    if(d_exp.indexIn(expr, 0) != -1)
    {
        left_expr = expr.section(d_exp, 0, 0).simplified();
        right_expr = expr.section(d_exp, 1, 1).simplified();
        if(left_expr.find(exp) != -1 && !left_expr.isEmpty() && ls.indexOf(left_expr) == -1) ls.append(left_expr);
        else buildString(left_expr, ls);
        if(right_expr.find(exp) != -1 && !right_expr.isEmpty() && ls.indexOf(right_expr) == -1) ls.append(right_expr);
        else buildString(right_expr, ls);
        if(!left_expr.isEmpty()) expr.replace(left_expr, "#val");
        if(!right_expr.isEmpty()) expr.replace(right_expr, "#val");
        if(!expr.isEmpty()) buildString(expr, ls);
    }
    else
    {
        left_expr = expr.section(exp, 0, 0).simplified();
        right_expr = expr.section(exp, 1, 1).simplified();
        if(!left_expr.isEmpty() && !right_expr.isEmpty() && right_expr.find(exp) == -1 &&
            left_expr.find(exp) == -1)
        {
            if(ls.indexOf(expr) == -1)  ls.append(expr);
            expr.clear();
        }
        else if(!left_expr.isEmpty() && left_expr.find(exp) != -1) buildString(left_expr, ls);
        else if(!right_expr.isEmpty() && right_expr.find(exp) != -1) buildString(right_expr, ls);
    }
}

/// Определение выполняемой сложной функции и помощь в формировании строки
void CompParamDescr::determDifficultOp(QString& expr, QStringList& ls, const QRegExp& df_exp)
{
    QString left_expr = "", right_expr = "", parameters = "";
    const char *simple_op_low_priority = "[+-]", *simple_op_high_priority = "[*/]";
    QRegExp exp_low(simple_op_low_priority), exp_high(simple_op_high_priority);
    parameters = expr.section(df_exp, 1, 1).simplified();;
    left_expr = parameters.section(",", 0, 0).simplified();
    right_expr = parameters.section(",", 1, 1).simplified();

    if(left_expr.find(exp_low) != -1) determOperation(left_expr, ls, exp_low, exp_high);
    else if(left_expr.find(exp_high) != -1) determOperation(left_expr, ls, exp_high, exp_low);
    if(right_expr.find(exp_low) != -1) determOperation(right_expr, ls, exp_low, exp_high);
    else if(right_expr.find(exp_high) != -1) determOperation(right_expr, ls, exp_high, exp_low);

    left_expr = parameters.section(",", 0, 0).simplified();
    right_expr = parameters.section(",", 1, 1).simplified();
    if((expr.find(exp_low) != -1 || expr.find(exp_high) != -1))
    { expr.replace(left_expr, "#val");        expr.replace(right_expr, "#val"); }
    if(expr.find(df_exp) != -1) ls.append(expr);
}

/// Удаление скобок
QString CompParamDescr::remove_symbols(const char* op, QString expr)
{
    if(strlen(op) < 2) return expr;
    QString e = expr;
    int pos = e.find("(");
    e = e.replace(pos, 1, " ").simplified();
    pos = e.lastIndexOf(")");
    e = e.remove(pos, 1).simplified();

    return e;
}

/// Вычисление большой формулы
COMPUTE* ElemFormul::calculateFormul(LOGRECORD* record, vector<ParamDescr*>* vec)
{
    COMPUTE* result = 0;
    int size = formul_list.size();
    QList<double> result_values;
    for(int i=0; i<size; ++i)
        result = calc(record, vec, formul_list, result_values);

    return result;
}

/// Получение индекса нужного параметра
int ElemFormul::argumentIndex(std::vector<ParamDescr*>* vec, QString arg)
{
    int index = -1, i = 0;
    if(isNumber(arg)) return index;
    string ar = arg.toStdString();
    for(paramI iter=vec -> begin(); iter!=vec -> end(); ++iter, ++i)
        if((*iter) -> Name() == ar)
        {
            index = i;
            break;
        }
    
    return index;
}

/// Вычисление простейших формул
COMPUTE* ElemFormul::calc(LOGRECORD* record, vector<ParamDescr*>* vec, QStringList& ls, QList<double>& rs_vl)
{
    if(ls.empty()) return 0;
    QString formul = ls.takeFirst();
    COMPUTE* result = new COMPUTE();
    QRegExp exp(BASE_OPERATIONS);
    if(formul.find(exp) != -1)
    {
        string op = exp.capturedTexts().at(0).toStdString();
        result -> op = op;
        QString arg1 = "", arg2 = "";
        if(op.size() < 2)
        {
            arg1 = formul.section(op.c_str(), 0, 0).simplified();
            arg2 = formul.section(op.c_str(), 1, 1).simplified();
        }
        else
        {
            QString parameters = formul.section(op.c_str(), 1, 1).simplified();
            arg1 = parameters.section(",", 0, 0).simplified();
            arg2 = parameters.section(",", 1, 1).simplified();
        }
        if(isNumber(arg1)) result -> arg1 = arg1.toDouble();
        if(isNumber(arg2)) result -> arg2 = arg2.toDouble();
        result -> arg1_index = argumentIndex(vec, arg1);
        result -> arg2_index = argumentIndex(vec, arg2);
        if(result -> arg1_index != -1) if(record -> params[result -> arg1_index].status == PS_OK)
            result -> arg1 = record -> params[result -> arg1_index].value;
        if(result -> arg2_index != -1) if(record -> params[result -> arg2_index].status == PS_OK)
            result -> arg2 = record -> params[result -> arg2_index].value;
        if(arg2.find("#val") != -1 && arg1.find("#val") != -1) rs_vl.append(result -> GetValue());
        int sz = rs_vl.size();
        if(arg2.find("#val") != -1) result -> arg2 = (!rs_vl.empty()) ? rs_vl.takeFirst() : 1.0;
        if(arg1.find("#val") != -1) result -> arg1 = (!rs_vl.empty()) ? rs_vl.takeFirst() : 1.0;
    }

    if(!ls.empty())
    {
        string next = ls.first().toStdString();
        double vl = result -> GetValue();
        if(next.find("#val") != -1) rs_vl.append(vl);
    }

    return result;
}


////////////////////////////////////////////////////////////////////////////////////////////
// Применение данных разработанных функций

/// Инициализация вычислимых параметров
void IniReader::InitComp(string& rec, vector<ParamDescr*>& rec_descr)
{
    CompParamDescr* p = new CompParamDescr();
    QString r = rec.c_str();

    string name = r.section('=', 0, 0).simplified().toLower().toStdString();
    p -> Name(name);
    p -> Address(1000);
    p -> ParamType("t_comp");
    string expression = r.section('=', 1, 1).simplified().toLower().toStdString();
    p -> Expr(expression);
    p -> addFormul();

    rec_descr.push_back(p);
}

/// Заполнение вычислимых параметров
void LogReader::FillCompParams(LOGRECORD& t)
{
    int size = rec_descr.size();
    for(int i=indexCompParam; i<rec_descr.size(); ++i)
    {
        CompParamDescr* p = dynamic_cast<CompParamDescr*> (rec_descr[i]);
        ElemFormul formul(p -> formulList());
        COMPUTE* element = formul.calculateFormul(&t, &rec_descr);
        if(element != 0)
        {
            t.params[i].value = element -> GetValue();
            t.params[i].status = PS_OK;
            t.params[i].evn = 0;
        }
    }
}

Небольшие пояснения.
buildString(QString& expr, QStringList& ls) - функция из исходной строки с математическим выражением формирует список строк такого типа:
"H1 + H2"
"H1/H2"
"H1*H2"
"H1 - H2"
"GetHMax lat, lon" - спец.операция (назовем так) - короче вызывает одноименную функцию с данными параметрами.

calc(LOGRECORD* record, vector<ParamDescr*>* vec, QStringList& ls, QList<double>& rs_vl)- функция отыскивает значения параметров и вычисляет эти простейшие выраженя.

Сообщение отредактировал AD - 26.9.2008, 18:14

Причина редактирования: длинный код оборачивайте в тэг expand

[AD]

Скорее всего, что QtScript мне придется использовать совсем в другом проекте, который начал делать.
Для выполнения sql-скриптов. Буду благодарен, если дадите ссылочки, где почитать, про это.

[Litkevich Yuriy]

А то критика типа ЛАЖА, ФИГНЯ или же типа такой

Да у нас это вроде не практикуется

[AD]

А то критика типа ЛАЖА, ФИГНЯ или же типа такой

Да у нас это вроде не практикуется

[offtop]
Своевременно подметил!
[/offtop]

[bugsstring]

люди, а никто не писал что-то типа генератора формул ? Чтоб строку в картинку переганять (что-то типа OOo Math) ?

[Tonal]

Может Tex поможет?

[bugsstring]

Может Tex поможет?

в том то и дело, что желательно без Теха или ЛаТеха ((
просто не факт, что на машинке куды приложение будет установлено будет в наличии что-то подобное...
в принципе буду копать в сторону MathML, но проблема на столько "распарсить" строку, сколько потом это все отрендерить...

Вот гадство

1. how can i use mathml in qt??
2. how will the equations be displayed ??
3. how can i read or write in to mml
(i.e.,mathml)files??

Ответ

Only if you have an Enterprise license, otherwise you'll need to write your
own parser/displayer using the XML classes.

может попробовать реализовать самостоятельно ? ))))
доки ж есть

http://doc.trolltech.com/solutions/4/qtmml...tmmlwidget.html

пример использования.....
ММЛ браузер