Молодогвардейцев 454015 Россия, Челябинская область, город Челябинск 89085842764
MindHalls logo

Реализация парсера математических выражений на С++

Доброго времени суток, дорогие гости! Сегодня мы будем программировать одну очень интересную штуку. Алгоритм распознавания и вычисления математических выражений, проще говоря, парсер. Он очень активно использует постфиксную запись выражения, о ней мы тоже поговорим, и научимся программно ее получать.

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

Итак, кто же такой парсер и чем он занимается? Давайте разбираться.

Задача

Наш парсер математических выражений должен уметь распознавать и вычислять такие операции:
— сложение, вычитание, умножение, деление;
— возведение в степень, остаток от деления(%);
— факториал;
— логическое И, логическое ИЛИ, логическое отрицание;
— синус, косинус, тангенс, арксинус, арккосинус, арктангенс;

Кроме того, необходима поддержка переменных и массивов. Он должен без труда выдать ответ, например, на такое выражение(мудрить не стал, пример простенький).

(2 + 2) * 5 + 2 + num1 + mas[0]
num1=3
mas{9}

Информация считывается из файла. Тут же можно рассказать про синтаксис. Первой строкой всегда должно быть само арифметическое выражение, можно с пробелами. Дальше объявления всех переменных и массивов, вида ‘num=value’ для переменных и mas{value1,value2,…} для массивов соответственно. С первого взгляда мне показалось, что ничего сложного. Обычный калькулятор, правда, вычисляющий за раз несколько операций. Однако, спустя десять страниц поиска я понял, что не все так тривиально.

Решение

Алгоритм распознавания математических выражений сводится к трем основным этапам:

  1. считывание выражения и инициализация всех переменных и массивов, если они есть;
  2. преобразование выражения в постфиксную запись;
  3. вычисление значения выражения.

Разберем каждый этап подробнее и посмотрим его реализацию.

Считывание математического выражения

На первом этапе алгоритм считывает файл, запоминает выражение и получает значения всех переменных и массивов. Выражение это простая строка(string), переменные — ассоциативный массив  map<string, double>, «массив массивов» — map<string, vector<double>>. Имя переменной считываем до «=», имя массива до «{«. На этом подготовительный этап окончен.

Исходный код  на C++

//Массив переменных
typedef map<string, double> Variables;
//Массив "массивов"
typedef map<string, vector<double> > Massives;

//Функция считывает выражение в строку "expr" и ищем переменные или массивы
void ReadExpressionFromStream(ifstream &inp, string &expr, Variables &var, Massives &mas) {
    getline(inp, expr);
    string temp;
    int pos;

    while (!inp.eof()) {
        getline(inp, temp);
        //Если встретили '=', то это переменная, заносим ее имя и значение в массив
        pos = temp.find('=');
        if(pos>0) {
            string name = temp.substr(0, pos);
            double value = atof(temp.substr(pos + 1).c_str());
            var[name] = value;
        }
        //Если нашли '{', это массив, заносим имя массива и значения в соответствующие массивы
        pos = temp.find('{');
        if(pos>0) {
            string name = temp.substr(0,pos);
            //Ищем значения массива и запоминаем их
            int pos1=pos, pos2;
            do {
                pos2 = temp.find(',');
                double value = atof(temp.substr(pos1+1, pos2).c_str());
                mas[name].push_back(value);
                if(pos2 == -1)
                        break;
                temp[pos2] = ' ';
                pos1 = pos2;
            }while (pos2 > 0);
        }
    }
    return;
}

Постфиксная запись математического выражения

Для того, чтобы алгоритм смог понять и вычислить выражение, его нужно перевести в постфиксную запись. Это такая запись математического выражения, в которой операция указывается после свои операндов. Рассмотрим постфиксную запись нашего примера.

Было:
(2 + 2) * 5 + 2 + num1 + mas[0]
Стало:
2 2 + 5 * 2 + num1 + 0 mas +

Читаем слева направо. С массивом, возможно, не совсем понятно, но это работает следующим образом: имя массива выступает в роли функции, получает аргументом индекс и возвращает значение. Давайте рассмотрим алгоритм получения такой записи.

Алгоритм преобразования выражения в постфиксную запись

Предположим, что наше выражение разбито на токены. Токен это отдельная самостоятельная единица в выражении, например, константа, имя переменной или операция.

Заводим стек для токенов. Просматриваем выражение слева направо. Если очередной токен это:
— переменная, то записываем ее в результирующую строку(строка с постфиксной записью);
— открывающая круглая скобка, то кладем ее в стек;
— закрывающая скобка, то записываем в результирующую строку из стека все, что до открывающей скобки, которую удаляем из стека;
— операция, то записываем в результирующую строку из стека все операции с большим или равным приоритетом, до тех пор, пока стек не опустеет, либо не встретится открывающая скобка, либо не встретится операция с меньшим приоритетом;
— все остальное просто помещаем в результирующую строку.

Исходный код алгоритма на C++

Функция расчленения на токены

// Типы токенов
enum tokentype {
    //Переменная, константа, (, ), функция, операция, массив, {, }
    var, num, op_br, cl_br, func, op, mas, op_sbr, cl_sbr
};
// Структура токена
struct token {
    string name;
    tokentype type;

    //Конструкторы
    token(string str, tokentype typ) {
        name = str;
        type = typ;
    }
    token() {}
};
//Массив токенов
typedef vector<token> tokens;
//Множество разделителей
set<char> DelimSet;
//Разделители
const string delimiters = " ()+/*-^&|!%[]";
//Инициализирует множество разделителей
void CreateSetOfDelimiters() {
    for (int i = 0; i < delimiters.size(); i++)
        DelimSet.insert(delimiters[i]);
    return;
}

//Проверка, является ли символ разделителем
bool IsDelimiter(char sym) {
    return DelimSet.count(sym) > 0;
}

//Разбиваем выражение на токены
void CreateTokensFromExpression(string &expr, tokens &texpr) {
    CreateSetOfDelimiters();
    string ex = expr + " ";
    string name;

    //Получаем имя токена
    int i = 0;
    while (i < ex.size() - 1) {
        name = "";
        //Если текущий символ разделитель
        if (IsDelimiter(ex[i])) {
            if (ex[i] == ' ') { //Пробел просто перепрыгиваем
                i++;
                continue;
            }
            name = ex[i]; //Любой другой добавляем в имя токена
            i++;
        }

        else {
            while (!IsDelimiter(ex[i])) {
            /*Если не разделитель непример, переменная или имя массива,
            Считываем его польностью */
                name += ex[i];
                i++;
            }
        }
        //Заносим получившийся токен в список токенов
        texpr.push_back(token(name, var));
    }

    //Раздаем получившимся токенам типы
    for (int j = 0; j < texpr.size(); j++) {
        if (texpr[j].name[0] == '[') {
            texpr[j].type = op_sbr;
            continue;
        }
        if (texpr[j].name[0] == ']') {
            texpr[j].type = cl_sbr;
            continue;
        }
        if (texpr[j].name[0] == '(') {
            texpr[j].type = op_br;
            continue;
        }
        if (texpr[j].name[0] == ')') {
            texpr[j].type = cl_br;
            continue;
        }
        if (isdigit(texpr[j].name[0])) {
            texpr[j].type = num;
            continue;
        }

        //mas
        if (isalpha(texpr[j].name[0])) {
            if(j < texpr.size() - 1 && texpr[j+1].name[0] == '[')
                texpr[j].type = mas;
            //continue;
        }

        if (isalpha(texpr[j].name[0])) {
            if (j < texpr.size() - 1 && texpr[j+1].name[0] == '(')
                texpr[j].type = func;
            continue;
        }

        texpr[j].type = op;
    }

    //Проверяем минус и !, что это префиксные операции
    for (int j = 0; j < texpr.size(); j++) {
        if (texpr[j].name == "-" && (j == 0 || texpr[j - 1].type == op_br))
            texpr[j].name = "opposite";
        if (texpr[j].name == "!" && (j == texpr.size()-1 || texpr[j+1].type == cl_br || texpr[j+1].type == op))
            texpr[j].name = "factorial";
    }

    return;
}

Функция преобразования в постфиксную запись

//Приоритеты операций
map <string, int> prior;
//Функция выставляет приоритеты операций
void CreatePrior() {
    prior["+"] = 10;
    prior["-"] = 10;
    prior["*"] = 20;
    prior["/"] = 20;
    prior["^"] = 30;
    prior["opposite"] = 10;
    prior["factorial"] = 30;
    prior["%"] = 20;
    prior["&"] = 5;
    prior["|"] = 5;
    prior["!"] = 40;
}

//Переводим выражение в постфиксную запись
void CreatePostfixFromTokens(tokens &texpr, tokens &pexpr) {
    //Задаем приоритеты операций
    CreatePrior();
    stack <token> TStack;

    //Ловим токены и работаем по алгоритму
    for (int i = 0; i < texpr.size(); i++) {
        switch (texpr[i].type) {
            case var:
            case num:
                pexpr.push_back(texpr[i]);
                break;

            case op_br:
                TStack.push(texpr[i]);
                break;

            case cl_br:
                while (TStack.top().type != op_br) {
                    pexpr.push_back(TStack.top());
                    TStack.pop();
                }
                TStack.pop();
                break;

            case op_sbr:
                TStack.push(texpr[i]);
                break;

            case cl_sbr:
                while (TStack.top().type != op_sbr) {
                    pexpr.push_back(TStack.top());
                    TStack.pop();
                }
                TStack.pop();
                break;

            case op:
                if (TStack.size()) {
                    while (TStack.size() && ((TStack.top().type == op && prior[texpr[i].name] <= prior[TStack.top().name]) ||
                        TStack.top().type == func ||
                        TStack.top().type == mas)) {
                        pexpr.push_back(TStack.top());
                        TStack.pop();
                    }
                }
                TStack.push(texpr[i]);
                break;

            case mas:
                while (TStack.size() && TStack.top().type == mas) {
                    pexpr.push_back(TStack.top());
                    TStack.pop();
                }
                TStack.push(texpr[i]);
                break;

            case func:
                while (TStack.size() && TStack.top().type == func) {
                    pexpr.push_back(TStack.top());
                    TStack.pop();
                }
                TStack.push(texpr[i]);
                break;
        }
    }

    while (TStack.size()) {
        pexpr.push_back(TStack.top());
        TStack.pop();
    }

    return;
}

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

Заводим стек и просматриваем постфиксную запись слева направо. Если очередной член это:
— константа или переменная, то заносим ее значение в стек;
— операция или функция, то извлекаем из стека необходимое количество операндов, применяем к ним операцию(функцию) и заносим результат обратно в стек.

На вершине останется единственное значение — результат нашего выражения.

Каждая операция это отдельная функция, принимающая на вход стек. Они будут лежать в ассоциативном массиве map<string, func_type>. Далее действуем строго по алгоритму и получаем на вершине стека результат выражения.

Исходный код на C++

Функция вычисления значения

//Указатель на функцию(для операций)
typedef double(*func_type)(stack<double> &);

//Массив операций
typedef map<string, func_type> Ops;
Ops ops;

//Инициализация массива операций
void CreateOps() {
    ops["+"] = op_plus;
    ops["-"] = op_minus;
    ops["*"] = op_mul;
    ops["/"] = op_div;
    ops["^"] = op_deg;
    ops["opposite"] = op_opposite;
    ops["factorial"] = op_factorial;
    ops["%"] = op_odiv;
    ops["&"] = op_and;
    ops["|"] = op_or;
    ops["!"] = op_not;
    ops["sin"] = op_sin;
    ops["cos"] = op_cos;
    ops["tan"] = op_tan;
    ops["acos"] = op_acos;
    ops["asin"] = op_asin;
    ops["atan"] = op_atan;

    return;
}

//Считаем результат выражения
double ResultExpr(tokens &pexpr, Variables &expvars, Massives &varmas) {
    CreateOps();
    stack <double> s;

    for (int i=0; i<pexpr.size(); i++) {
        switch(pexpr[i].type) {
            case num: {
                s.push(atoi(pexpr[i].name.c_str()));
                }
                break;

            case var: {
                    Variables::iterator Vit;
                    for(Vit=expvars.begin(); Vit!=expvars.end(); Vit++) {
                        if(Vit->first == pexpr[i].name) {
                            s.push(Vit->second);
                            break;
                        }
                    }
                }
                break;

            case func:
            case op: {
                    Ops::iterator Oit;
                    for(Oit=ops.begin(); Oit!=ops.end(); Oit++) {
                        if(Oit->first == pexpr[i].name) {
                            s.push(Oit->second(s));
                            break;
                        }
                    }
                }
                break;

            case mas: {
                int index = s.top();
                s.pop();

                Massives::iterator it;
                for(it = varmas.begin(); it != varmas.end(); it++) {
                    if(it->first == pexpr[i].name)
                        s.push(it->second[index]);
                }
            }
        }
    }

    return s.top();
}

Реализация операций

//Реализация доступных операций
double fact(double n) {
    if(n == 0)
        return 1;
    return n*fact(n-1);
}
double op_plus(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return a+b;
}
double op_minus(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return b-a;
}
double op_mul(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return a*b;
}
double op_div(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return b/a;
}
double op_deg(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    //b^a!!
    return pow(b,a);
}
double op_opposite(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return -a;
}
double op_factorial(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return fact(a);
}
double op_odiv(stack <double> &s) {
    long long a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return b%a;
}
double op_and(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return a&&b;
}
double op_or(stack <double> &s) {
    double a,b;
    a = s.top();
    s.pop();
    b = s.top();
    s.pop();
    return a||b;
}
double op_not(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return !a;
}
double op_sin(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return sin(a);
}
double op_cos(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return cos(a);
}
double op_tan(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return tan(a);
}
double op_asin(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return asin(a);
}
double op_acos(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return acos(a);
}
double op_atan(stack <double> &s) {
    double a;
    a = s.top();
    s.pop();
    return atan(a);
}

Функция main

int main() {
    tokens texpr, pexpr;
    Variables expvars;
    Massives expmasvars;
    string expr;
    ifstream file("test.txt");

    ReadExpressionFromStream(file, expr, expvars, expmasvars);

    cout << "Expr:" << endl;
    cout << expr << endl;

    Variables::iterator it;
    for (it = expvars.begin(); it != expvars.end(); it++)
        cout << it->first << '=' << it->second << endl;

    Massives::iterator it1;
    for (it1 = expmasvars.begin(); it1 != expmasvars.end(); it1++) {
        cout << it1->first << '{';
        for(int i=0; i<it1->second.size(); i++) {
            if(i == it1->second.size()-1)
                cout << it1->second[i];
            else
                cout << it1->second[i] << ',';
        }
        cout << '}' << endl;
    }
    cout << endl;


    CreateTokensFromExpression(expr, texpr);

    cout << "Token:" << endl;
    for (int i = 0; i < texpr.size(); i++)
        cout << texpr[i].name << ' ';
    cout << endl << endl;

    CreatePostfixFromTokens(texpr, pexpr);

    cout << "Pexpr:" << endl;
    for (int i = 0; i < pexpr.size(); i++)
        cout << pexpr[i].name << ' ';
    cout << endl << endl;

    cout << "Result:" << endl;
    cout << ResultExpr(pexpr, expvars, expmasvars) << endl;

    return 0;
}

Заключение

Запрограммировали вполне солидный парсер математических выражений. Массивы были добавлены не сразу, а в качестве дополнительного задания на смекалку. Большой плюс этой программы в том, что она легко расширяема, можно спокойно добавить операций или поддержку функций. Очень уж не хотелось, чтобы этот проект пропал среди прочих университетских. В будущем буду делиться другими интересными проектами. На это все, спасибо за внимание!

  • А мы в университете массивы в ку-бэйсике сортировали… Я бы лучше чем-то таким занялся)