Доброго времени суток, дорогие гости! Сегодня мы будем программировать одну очень интересную штуку. Алгоритм распознавания и вычисления математических выражений, проще говоря, парсер. Он очень активно использует постфиксную запись выражения, о ней мы тоже поговорим, и научимся программно ее получать.
Программа была написана мной на втором курсе, сразу после реализации стека, в качестве учебного задания. В принципе, к ней можно добавить графический интерфейс и получить полноценный калькулятор, вычисляющий целые арифметические выражения, но я не стал.
Итак, кто же такой парсер и чем он занимается? Давайте разбираться.
Задача
Наш парсер математических выражений должен уметь распознавать и вычислять такие операции:
— сложение, вычитание, умножение, деление;
— возведение в степень, остаток от деления(%);
— факториал;
— логическое И, логическое ИЛИ, логическое отрицание;
— синус, косинус, тангенс, арксинус, арккосинус, арктангенс;
Кроме того, необходима поддержка переменных и массивов. Он должен без труда выдать ответ, например, на такое выражение(мудрить не стал, пример простенький).
(2 + 2) * 5 + 2 + num1 + mas[0]
num1=3
mas{9}
Информация считывается из файла. Тут же можно рассказать про синтаксис. Первой строкой всегда должно быть само арифметическое выражение, можно с пробелами. Дальше объявления всех переменных и массивов, вида ‘num=value’ для переменных и mas{value1,value2,…} для массивов соответственно. С первого взгляда мне показалось, что ничего сложного. Обычный калькулятор, правда, вычисляющий за раз несколько операций. Однако, спустя десять страниц поиска я понял, что не все так тривиально.
Решение
Алгоритм распознавания математических выражений сводится к трем основным этапам:
- считывание выражения и инициализация всех переменных и массивов, если они есть;
- преобразование выражения в постфиксную запись;
- вычисление значения выражения.
Разберем каждый этап подробнее и посмотрим его реализацию.
Считывание математического выражения
На первом этапе алгоритм считывает файл, запоминает выражение и получает значения всех переменных и массивов. Выражение это простая строка(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;
}
Заключение
Запрограммировали вполне солидный парсер математических выражений. Массивы были добавлены не сразу, а в качестве дополнительного задания на смекалку. Большой плюс этой программы в том, что она легко расширяема, можно спокойно добавить операций или поддержку функций. Очень уж не хотелось, чтобы этот проект пропал среди прочих университетских. В будущем буду делиться другими интересными проектами. На это все, спасибо за внимание!