MyTetra Share
Делитесь знаниями!
Еще один пример простого парсера математических выражений, с поддержкой именованных констант
Время создания: 18.10.2023 11:17
Автор: Xintrea
Текстовые метки: c++, qt, парсер, математическое, выражение, формула, константа, переменная, алгоритм, польская, нотация, библиотека
Раздел: Компьютер - Программирование - Язык C++ (Си++)
Запись: xintrea/mytetra_syncro/master/base/16976170298dgx4ikg8x/text.html на raw.github.com

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


Предполагается, что перед вычислением математического выражения парсеру задается таблица значений именованных констант, например так:



QMap<QString, QString> constants;

constants["pi"] ="3.1415";

constants["ten"] ="10";

constants["ourConstanta"]="25+ten";


MathParser mathParser;

mathParser.setConstantsTable( constants );



Как можно заметить, значение некоторых констант может зависеть от значения других констант.


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



float result1=mathParser.calculate("1+pi+ten+ourConstanta");


if(!mathParser.isCalculateError())

{

qDebug() << "Result 1: " << result1;

}

else

{

qDebug() << "Error at expression 1 parse";

}



float result2=mathParser.calculate("2+incorrectConstanta");


if(!mathParser.isCalculateError())

{

qDebug() << "Result 2: " << result2;

}

else

{

qDebug() << "Error at expression 2 parse";

}



Результат работы кода будет следующим:



Result 1: 49.1415


Found unavailable constant name "incorrectConstanta"

Error at expression 2 parse



Сам код парсера с поддержкой именованных констант (кто-то может называть их переменными) выглядит следующим образом.



Файл math_parser.h



#include <algorithm>

#include <iostream>

#include <string>

#include <cctype>

#include <iterator>


#include <QString>

#include <QMap>

#include <QHash>


using namespace std;



class MathParser

{


public:

MathParser();

virtual ~MathParser();


bool setConstantsTable( QMap<QString, QString> constantsTable );

float calculate(const QString &text);


bool isCalculateError();


private:


float constantCalculate(const QString &text);

QString createDirectPolkaNote(const QString &text);

float calculateByDirectPolkaNote(QString polkaNote, bool isConstantCalculate);


bool m_isCalculateError=false;

QHash<QString, float> m_constantsTable;

};



// Представление математического выражения в виде дерева

class Exp

{


public:


Exp(){}

virtual ~Exp(){}


virtual string print(){ return ""; }

virtual void release(){}


static Exp* strToExp(string &str); // Построитель абстрактного дерева из строки

};



// Конечный элемент абстрактного дерева

class Term : public Exp

{

public:


Term(string v) : val(v){}


string print();

void release(){}


private:


string val;

};



// Узел абстрактного дерева

class Node : public Exp

{

public:


Node(char op, Exp* left, Exp* right) : op(op), l_exp(left), r_exp(right){}

~Node(){}


string print();

void release();


private:


char op; // Возможные значения +, -, *, /

Exp *l_exp;

Exp *r_exp;

};



Файл math_parser.cpp



#include <QString>

#include <QStringList>

#include <QDebug>


#include "math_parser.h"


using namespace std;



MathParser::MathParser()

{


}



MathParser::~MathParser()

{


}



bool MathParser::setConstantsTable(QMap<QString, QString> constantsTable)

{

m_constantsTable.clear();


// Проверка повторяющихся имен констант

QList<QString> allNames=constantsTable.keys(); // Все имена констант

QList<QString> uniqueNames=constantsTable.uniqueKeys(); // Уникальные имена констант

if( allNames.size()!=allNames.size() )

{

for(int i=0; i<allNames.size(); ++i)

{

if(allNames.value(i)!=uniqueNames.value(i))

{

qWarning() << "Can't use constant table. Detect double constant name "

<< allNames.value(i);

return false;

}

}

}


int tryCount=0;

int tryTreshold=constantsTable.size()*10;

do

{

// Расчет значений констант,

// исключение посчитанных констант из входящего "сырого" набора

// и добавление посчитанных констант в итоговую таблицу значений констант

auto i=constantsTable.begin();

while(i!=constantsTable.end())

{

float result=this->constantCalculate( i.value() );


// Если выражение константы успешно преобразовано в число

if( !m_isCalculateError )

{

// Значение константы запоминается

m_constantsTable[ i.key() ]=result;


// Константа исключается из входящего "сырого" набора

i=constantsTable.erase( i );

}

else

{

++i;

}

}


if( tryCount>tryTreshold )

{

qWarning() << "Can't calculate constants values in constant table. "

<< "May be loop declare in constant "

<< constantsTable.keys().value(0);

return false;

}

++tryCount;


} while( constantsTable.size()!=0 );


// Все значения констант были успешно посчитаны

return true;

}



// Вычисление значения константы из строки

float MathParser::constantCalculate(const QString &text)

{

m_isCalculateError=false;


QString polkaNote=this->createDirectPolkaNote(text);


return this->calculateByDirectPolkaNote(polkaNote, true);

}



// Вычисление результата математического выражения из строки

float MathParser::calculate(const QString &text)

{

m_isCalculateError=false;


QString polkaNote=this->createDirectPolkaNote(text);


return this->calculateByDirectPolkaNote(polkaNote, false);

}



bool MathParser::isCalculateError()

{

return m_isCalculateError;

}



// Создание строки с прямой польской ноцией

QString MathParser::createDirectPolkaNote(const QString &text)

{

// Для последующей передачи ссылки на std::string, строка должна существовать

string exp=text.toStdString();


// Удаление лишних пробелов

exp.erase(remove_if(exp.begin(), exp.end(), ::isspace), exp.end());


// Построение дерева

Exp *tree = Exp::strToExp(exp);


if(!tree)

{

m_isCalculateError=true;

qDebug() << "Incorrect math expression: " << QString(exp.c_str());

return QString();

}


// Получение прямой польской нотации с пробелами и скобками

QString polkaNote=tree->print().c_str();

// qDebug() << "Infix: " << QString(exp.c_str()) << " Polka notation: "<< QString(tree->print().c_str());


// Очистка дерева

tree->release();

delete tree;


return polkaNote;

}



// Вычисление результата математического выражения из строки с прямой польской нотацией

float MathParser::calculateByDirectPolkaNote(QString polkaNote, bool isConstantCalculate)

{

// Убираются скобки, в прямой польской нотации для алгоритма прохода по выражению они не нужны

polkaNote=polkaNote.remove("(");

polkaNote=polkaNote.remove(")");


// Список частей выражения в польской нотации

QStringList chunks=polkaNote.split(" ", QString::SkipEmptyParts);

// qDebug() << chunks;


const QStringList availableOperation=QStringList() << "+" << "-" << "*" << "/";



// Замена имен констант на их числовые значения в выражении с польской нотацией

for(int i=0; i<chunks.size(); ++i)

{

QString chunk=chunks[i];


// Если текущая часть выражения не оператор

if( !availableOperation.contains( chunk ))

{

bool ok = true;

chunk.toFloat(&ok);


// Если текущая часть выражения не может быть приведена к числу

if( !ok )

{

// Значит текущая часть выражения должна быть именованной константой

if( m_constantsTable.contains(chunk) )

{

// Вместо имени константы подставляется число

chunks[i]=QString::number( static_cast<double>(m_constantsTable[chunk]) );

}

else

{

// Если происходит вычисление значения константы (а не пользовательского выражения),

// то может быть ситуация что еще неизвестно значение другой константы,

// от которой зависит текущая константа, и это нормально.

// Предупреждение нужно выводить только если идет расчет пользовательского выражения

if(!isConstantCalculate)

{

qWarning() << "Found unavailable constant name " << chunk;

}


m_isCalculateError=true;

return 0;

}

}

}

}



// Алгоритм: пробегать по списку от конца к началу.

// Если найден оператор, справа от него берутся два операнда и расчитывается значение.

// Расчитанное значение кладется в список на место оператора, операнды удаляются из списка

// Действие повторяется, пока размер списка не станет равным единице,

// и в нем будет итоговое значение


while(chunks.length() > 1)

{

int pointer = chunks.length();

QString symbol = "";


do

{

--pointer;

symbol=chunks[pointer];

}

while( !availableOperation.contains(symbol) );


float result = 0;

if(symbol == "+")

{

result = chunks[pointer+1].toFloat() + chunks[pointer+2].toFloat();

}

else if (symbol=="-")

{

if( chunks.length()!=2 )

{

result = chunks[pointer+1].toFloat() - chunks[pointer+2].toFloat();

}

else

{

// В конце расчета может возникнуть ситуация {"-", "число"}

result = 0 - chunks[pointer+1].toFloat();

}

}

else if (symbol=="*")

{

result = chunks[pointer+1].toFloat() * chunks[pointer+2].toFloat();

}

else if (symbol=="/")

{

result = chunks[pointer+1].toFloat() / chunks[pointer+2].toFloat();

}


// Результат кладется на место оператора

chunks[pointer]=QString::number(result);


// Удаляются операнды

chunks.removeAt(pointer+1); // Левый

if(chunks.length()>pointer)

{

chunks.removeAt(pointer+1); // Правый

}

}


return chunks[0].toFloat();

}



// Преобразование обычного (инфиксного) математического выражения в польскую нотацию

Exp* Exp::strToExp(string &str)

{

int level = 0;


// Обработка + или -

for(int i=str.size()-1; i>=0; --i){

char c = str[i];

if(c == ')'){

++level;

continue;

}

if(c == '('){

--level;

continue;

}

if(level > 0) continue;

if((c == '+' || c == '-') && i != 0 ){ // Если i==0 тогда s[0] содержит знак

string left(str.substr(0, i));

string right(str.substr(i+1));

return new Node(c, strToExp(left), strToExp(right));

}

}


// Обработка * или /

for(int i=str.size()-1; i>=0; --i){

char c = str[i];

if(c == ')'){

++level;

continue;

}

if(c == '('){

--level;

continue;

}

if(level>0) continue;

if(c == '*' || c == '/'){

string left(str.substr(0,i));

string right(str.substr(i+1));

return new Node(c, strToExp(left), strToExp(right));

}

}


// Рекурсивная обработка выражений в скобках

if(str[0] == '('){

for(int i=0; i<static_cast<int>(str.size()); ++i){

if(str[i] == '('){

++level;

continue;

}

if(str[i] == ')'){

--level;

if(level == 0){

string exp(str.substr(1, i-1));

return strToExp(exp);

}

continue;

}

}

} else // Иначе скобок нет, строка рассмативается как конечный узел

return new Term(str);


cerr << "Error: never execute point" << endl;

return nullptr;

}



string Term::print()

{

return string(" ")+val+string(" ");

}



string Node::print()

{

return string("(")+op+string(" ")+l_exp->print()+r_exp->print()+string(")");

}



void Node::release(){

l_exp->release();

r_exp->release();

delete l_exp;

delete r_exp;

}



Полный код консольного Qt-проекта прикреплен к статье.


Прикрепленные файлы:
Так же в этом разделе:
 
MyTetra Share v.0.60
Яндекс индекс цитирования