MyTetra Share
Делитесь знаниями!
Рабочий пример простого парсера математических выражений
Время создания: 16.07.2021 10:02
Автор: Xintrea
Текстовые метки: c++, парсер, математическое, выражение, синтаксическое дерево, польская нотация, parser
Раздел: Компьютер - Программирование - Язык C++ (Си++)
Запись: xintrea/mytetra_syncro/master/base/1626418975ycq3zktswn/text.html на raw.github.com

Иногда в проекте на Си++ необходимо иметь небольшой математический парсер. Он может пригодиться, например, для разбора математических выражений, которые прописываются в XML-конфиге программы.


Наиболее простые способы это сделать - либо воспользоваться C/C++ биндингами к скриптовым языкам программирования (например, можно интегрировать вызовы функций LUA или Perl), либо включить в проект готовую системную или стороннюю библиотеку математического парсинга (например, muparser, ExprTk или CMathParser). Однако бывают ситуации, когда сделать это невозможно: например, программа пишется для сертифицированной среды, в которой нет нужных библиотек и инструментов, а сторонние запрещены; либо использование ПО предполагается на очень ограниченных встраиваемых системах. Именно для таких ситуаций хорошо бы иметь небольшой самописный математический парсер.


В Интернете есть много информации по методам создания математических парсеров. Но, к сожалению, нет готового компактного решения, которое содержало бы в себе основной базис. Можно найти куски реализации того или иного аспекта разбора и преобразования математического выражения, но готовые реализации "всего вместе" можно пересчитать по пальцам. И эти реализации, зачастую, могут иметь фундаментальные странности - например тот же CMathParser заточен только под Windows и без правки исходного кода не будет работать в Linux, достаточно посмотреть на его заголовки:



#include <Windows.H>

#include <StdIO.H>

#include <StdLib.H>

#include <Math.H>

#include <Float.H>

#include <Limits.H>



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


Данный парсер содержит выдернутые из интернета реализации абстрактного синтаксического дерева (AST) и генератора прямой польской нотации (а не обратной, просто потому что первым рабочим примером была найдена именно эта парочка). Вычисление итогового значения по прямой польской нотации дописано самостоятельно с использованием библиотеки Qt, просто потому что в ней есть готовые удобные контейнерные классы, да и целевой проект написан на Qt. Перевод с Qt на STD этой части кода пусть будет домашним упражнением для студентов факультетов информатики.



Заголовок math_parser.h



#include <algorithm>

#include <iostream>

#include <string>

#include <cctype>

#include <iterator>


using namespace std;



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

class Exp

{


public:


Exp(){}

virtual ~Exp(){}


virtual void release(){}

virtual string print(){ return ""; }


static float calculate(string &exp);

static float calculate(const QString &exp);


private:


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

};



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

class Term : public Exp

{

public:


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


void release(){}

string print();


private:

string val;

};



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

class Node : public Exp

{

public:


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

~Node(){}


void release();

string print();


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;



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

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;

}



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

float Exp::calculate(const QString &exp)

{

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

string text=exp.toStdString();


return Exp::calculate( text );

}



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

float Exp::calculate(string &exp)

{

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

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


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

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


if(!tree)

{

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

return 0;

}


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

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

// qDebug() << "Infix: " << QString(exp.c_str());

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


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

tree->release();

delete tree;



// ---------------------------------

// Обработка прямой польской нотации

// ---------------------------------


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

polkaNote=polkaNote.remove("(");

polkaNote=polkaNote.remove(")");


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

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

// qDebug() << chunks;


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

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

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

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

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


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


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();

}



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;

}



Использование:



#include "math_parser.h"

...

QString mathExpression="1+2*3";

float result=Exp::calculate( mathExpression );



Кстати, неплохая теория (правда, с примерами на Паскале), изложена вот в этой статье: Практика разбора математических выражений: прямая польская запись.


Что касается обратной польской записи, то весьма компактный парсер на C++ приведен в статье Разбор математических выражений. Обратная польская нотация.



Так же в этом разделе:
 
MyTetra Share v.0.58
Яндекс индекс цитирования