Парсинг Сервис

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

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

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

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

Задача

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


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

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

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

Решение

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

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

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

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

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

Исходный код  на C++
//Массив переменных
typedef map Variables;
//Массив ""массивов""
typedef map 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 tokens;
//Множество разделителей
set DelimSet;
//Разделители
const string delimiters = "" ()+/*-^&|!%[]"";
//Инициализирует множество разделителей
void CreateSetOfDelimiters() {
for (int i = 0; i 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 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 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. Далее действуем строго по алгоритму и получаем на вершине стека результат выражения.

Исходный код на C++
Функция вычисления значения
//Указатель на функцию(для операций)
typedef double(*func_type)(stack &);
//Массив операций
typedef map 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 s;
for (int i=0; ifirst == 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 &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return a+b;
}
double op_minus(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return b-a;
}
double op_mul(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return a*b;
}
double op_div(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return b/a;
}
double op_deg(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
//b^a!!
return pow(b,a);
}
double op_opposite(stack &s) {
double a;
a = s.top();
s.pop();
return -a;
}
double op_factorial(stack &s) {
double a;
a = s.top();
s.pop();
return fact(a);
}
double op_odiv(stack &s) {
long long a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return b%a;
}
double op_and(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return a&&b;
}
double op_or(stack &s) {
double a,b;
a = s.top();
s.pop();
b = s.top();
s.pop();
return a||b;
}
double op_not(stack &s) {
double a;
a = s.top();
s.pop();
return !a;
}
double op_sin(stack &s) {
double a;
a = s.top();
s.pop();
return sin(a);
}
double op_cos(stack &s) {
double a;
a = s.top();
s.pop();
return cos(a);
}
double op_tan(stack &s) {
double a;
a = s.top();
s.pop();
return tan(a);
}
double op_asin(stack &s) {
double a;
a = s.top();
s.pop();
return asin(a);
}
double op_acos(stack &s) {
double a;
a = s.top();
s.pop();
return acos(a);
}
double op_atan(stack &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 }
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;
}
Заключение

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

Categories: Программирование, Реализации Tags: C++
15.10.201627.02.20172016-10-15T06:00:59+00:00Автор: Кузьминых Кирилл

Подписаться на обновления по электронной почте


Читайте также:
Параллельное умножение матриц с помощью OpenMP
Генерация случайных чисел на C/C++ с помощью rand()
Реализация алгоритма поиска в глубину на графе
Реализация и криптоанализ шифра гаммирования
Вычисление расстояния Хэмминга с помощью C++