Иногда в проекте на Си++ необходимо иметь небольшой математический парсер. Он может пригодиться, например, для разбора математических выражений, которые прописываются в 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++ приведен в статье Разбор математических выражений. Обратная польская нотация.

Для тех кому нужна поддержка именованных констант (переменных), можно посмотреть статью Еще один пример простого парсера математических выражений, с поддержкой именованных констант.