Парсер математических выражений
1,00
р.
Как написать парсер математических выражений? Надо реализовать не только операторы (+, -, /, *), но и функции, например log, sin, cos, tan и т.д.
Ответ
У математических выражений довольно простая структура - только бинарные операции ("+", "*" - два аргумента), унарные операции ("-", "sin" - один аргумент), и числа.
Один из наиболее простых способов написания парсера - это "рекурсивный спуск", т.е. написание парсера руками, без какого либо генератора парсеров (Bison, Boost.Spirit).
Хотя парсер может вычислять сразу выражение, обычно от парсера ожидается дерево операций, которое уже потом можно вычислить, или например напечатать. В простейшем виде элемент дерева выглядит так:
struct Expression { Expression(std::string token) : token(token) {} // Конструктор для чисел Expression(std::string token, Expression a) : token(token), args{a} {} // Конструктор унарных операций Expression(std::string token, Expression a, Expression b) : token(token), args{a, b} {} // Конструктор бинарных операций
std::string token // Операция или число std::vector args // Выражения - аргументы операции }
Парсер математических выражений можно описать с помощью трех основных функций:
парсер "токенов" - низкоуровневых элементов выражения - операций и чисел. Например 2, *, -, 1 для выражения 2 * -1. парсер простых выражений - числа, унарные операции, выражения в скобках. Например выражения 1, -1, (1+2). парсер бинарных выражений - два простых выражения, и бинарный оператор между ними. Например выражения 1 + 2, или 3 * (1+2).
Соответственно можно написать такой класс парсера:
class Parser { public: explicit Parser(const char* input) : input(input) {} // Конструктор, принимает строку с выражением Expression parse() // Основная функция парсинга private: std::string parse_token() // Парсит один токен Expression parse_simple_expression() // Парсит простое выражение Expression parse_binary_expression(int min_priority) // Парсит бинарное выражение
const char* input // Кусок строки, который еще не распарсили }
Функция-парсер токенов извлекает из строки один токен, и продвигает input вперед.
std::string Parser::parse_token() { // Пропускаем пробелы перед токеном. while (std::isspace(*input)) ++input
// Если input начинается с цифры, то парсим число. if (std::isdigit(*input)) { std::string number while (std::isdigit(*input) || *input == '.') number.push_back(*input++) return number }
// Список всех известных токенов - операции и скобки. static const std::string tokens[] = { "+", "-", "**", "*", "/", "mod", "abs", "sin", "cos", "(", ")" } for (auto& t : tokens) { if (std::strncmp(input, t.c_str(), t.size()) == 0) { input += t.size() return t } }
return "" // Какой-то неизвестный токен, или символ '\0' - конец строки. }
Имея парсер токенов, можно написать парсер простых выражений:
Expression Parser::parse_simple_expression() { // Парсим первый токен. auto token = parse_token() if (token.empty()) // Неожиданный конец строки, или неизвестный токен throw std::runtime_error("Invalid input")
if (std::isdigit(token[0])) // Если это цифра, возвращаем выражение без аргументов return Expression(token)
if (token == "(") { auto result = parse() if (parse_token() != ")") throw std::runtime_error("Expected ')'") return result // Если это скобки, парсим и возвращаем выражение в скобках }
// Иначе, это унарная операция ("-", "sin", и т.п.) auto arg = parse_simple_expression() // Парсим ее аргумент. return Expression(token, arg) }
И наконец, последняя и самая сложная часть - бинарные выражения. У бинарных операций есть приоритеты, например у + и - приоритет меньше чем у * и /, у ** (возведение в степень) приоритет больше чем у умножения. Напишем функцию, возвращающую приоритет бинарной операции:
int get_priority(const std::string& token) { if (token == "+") return 1 if (token == "-") return 1 if (token == "*") return 2 if (token == "/") return 2 if (token == "mod") return 2 // остаток от деления if (token == "**") return 3 // степень return 0 // Возвращаем 0 если токен - это не бинарная операция (например ")") }
Парсер бинарных выражений разбирает выражение в цикле, начиная с левой стороны. Выражение слева - это либо простое выражение, либо бинарное выражение, полученное на предыдущей итерации. Выражение справа получается рекурсивным вызовом парсера, при этом бинарные операции справа должны иметь больший приоритет чем текущая операция.
Expression Parser::parse_binary_expression(int min_priority) { auto left_expr = parse_simple_expression() // Парсим простое выражение.
for ( ) { auto op = parse_token() // Пробуем парсить бинарную операцию. auto priority = get_priority(op) // Выходим из цикла если ее приоритет слишком низок (или это не бинарная операция). if (priority <= min_priority) { input -= op.size() // Отдаем токен обратно, return left_expr // возвращаем выражение слева. }<br> // Парсим выражение справа. Текущая операция задает минимальный приоритет. auto right_expr = parse_binary_expression(priority) left_expr = Expression(op, left_expr, right_expr) // Обновляем выражение слева. } // Повторяем цикл: парсинг операции, и проверка ее приоритета. }
Функция parse() просто вызывает парсер бинарных выражений, передавая ему нулевой минимальный приоритет операций (любая бинарная операция):
Expression Parser::parse() { return parse_binary_expression(0) }
Для строки"3*4/5" код работает так:
Сначала left_expr парсится как простое выражение "3", затем парсится токен "*", его приоритет (2) больше минимального (0). Парсится выражение справа: делается вызов parse_binary_expression(2). Здесь input="4/5", left_expr парсится как "4", за ним идет токен с операцией "/", но теперь его приоритет 2 не больше минимального (2), цикл сразу же заканчивается, токен "/" возвращается обратно (input="/5"), возвращается выражение "4". Из правых и левых частей получается выражение ("*", "3", "4"), цикл повторяется. Опять парсится токен "/", его приоритет (2) больше минимального (0). Парсится выражение справа: вызов parse_binary_expression(2), при этом input = "5". left_expr парсится как "5", за ним идет пустой токен "" (конец строки). приоритет 0 меньше минимального (2), возвращается выражение "5". Из правых и левых частей получается выражение ("/", ("*", "3", "4"), "5"). Цикл повторяется, опять парсится пустой токен "", функция завершается.
Если приоритеты повышаются, например 2+3*4/5, то во вложенных вызовах parse_binary_expression успевает отработать дольше:
Парсится выражение слева "2" и операция "+" (приоритет 1). Для правой части делается вызов parse_binary_expression(1). Здесь всё как в предыдущем примере, input="3*4/5", только минимальный приоритет равен 1 а не 0. Цикл проходит несколько итераций, и мы получаем ("/", ("*", "3", "4"), "5") Дальше идут только пустые токены, т.к. input закончился. Выходим из цикла. Объединяем правую и левую части, получаем ("+", "2", ("/", ("*", "3", "4"), "5")).
Итак, у нас есть парсер. Но надо еще как-то вычислять результаты парсинга. Это можно сделать одной функцией:
double eval(const Expression& e) { switch (e.args.size()) { case 2: { // Два аргумента - бинарные операции. auto a = eval(e.args[0]) auto b = eval(e.args[1]) if (e.token == "+") return a + b if (e.token == "-") return a - b if (e.token == "*") return a * b if (e.token == "/") return a / b if (e.token == "**") return pow(a, b) if (e.token == "mod") return (int)a % (int)b throw std::runtime_error("Unknown binary operator") }
case 1: { // Один аргумент. auto a = eval(e.args[0]) if (e.token == "+") return +a if (e.token == "-") return -a if (e.token == "abs") return abs(a) if (e.token == "sin") return sin(a) if (e.token == "cos") return cos(a) throw std::runtime_error("Unknown unary operator") }
case 0: { // Числа (ноль аргументов). return strtod(e.token.c_str(), nullptr) } }
throw std::runtime_error("Unknown expression type") }
>>> Здесь <<< можно найти весь код целиком.<br>
Что делать если надо добавить функцию, которая принимает больше одного аргумента? - Функция, принимающая несколько аргументов - это функция принимающая один аргумент-кортеж (список). По этому самое простое решение - это ввести бинарную операцию "," (запятая), которая будет делать кортеж (список) чисел.
Ответ
У математических выражений довольно простая структура - только бинарные операции ("+", "*" - два аргумента), унарные операции ("-", "sin" - один аргумент), и числа.
Один из наиболее простых способов написания парсера - это "рекурсивный спуск", т.е. написание парсера руками, без какого либо генератора парсеров (Bison, Boost.Spirit).
Хотя парсер может вычислять сразу выражение, обычно от парсера ожидается дерево операций, которое уже потом можно вычислить, или например напечатать. В простейшем виде элемент дерева выглядит так:
struct Expression { Expression(std::string token) : token(token) {} // Конструктор для чисел Expression(std::string token, Expression a) : token(token), args{a} {} // Конструктор унарных операций Expression(std::string token, Expression a, Expression b) : token(token), args{a, b} {} // Конструктор бинарных операций
std::string token // Операция или число std::vector args // Выражения - аргументы операции }
Парсер математических выражений можно описать с помощью трех основных функций:
парсер "токенов" - низкоуровневых элементов выражения - операций и чисел. Например 2, *, -, 1 для выражения 2 * -1. парсер простых выражений - числа, унарные операции, выражения в скобках. Например выражения 1, -1, (1+2). парсер бинарных выражений - два простых выражения, и бинарный оператор между ними. Например выражения 1 + 2, или 3 * (1+2).
Соответственно можно написать такой класс парсера:
class Parser { public: explicit Parser(const char* input) : input(input) {} // Конструктор, принимает строку с выражением Expression parse() // Основная функция парсинга private: std::string parse_token() // Парсит один токен Expression parse_simple_expression() // Парсит простое выражение Expression parse_binary_expression(int min_priority) // Парсит бинарное выражение
const char* input // Кусок строки, который еще не распарсили }
Функция-парсер токенов извлекает из строки один токен, и продвигает input вперед.
std::string Parser::parse_token() { // Пропускаем пробелы перед токеном. while (std::isspace(*input)) ++input
// Если input начинается с цифры, то парсим число. if (std::isdigit(*input)) { std::string number while (std::isdigit(*input) || *input == '.') number.push_back(*input++) return number }
// Список всех известных токенов - операции и скобки. static const std::string tokens[] = { "+", "-", "**", "*", "/", "mod", "abs", "sin", "cos", "(", ")" } for (auto& t : tokens) { if (std::strncmp(input, t.c_str(), t.size()) == 0) { input += t.size() return t } }
return "" // Какой-то неизвестный токен, или символ '\0' - конец строки. }
Имея парсер токенов, можно написать парсер простых выражений:
Expression Parser::parse_simple_expression() { // Парсим первый токен. auto token = parse_token() if (token.empty()) // Неожиданный конец строки, или неизвестный токен throw std::runtime_error("Invalid input")
if (std::isdigit(token[0])) // Если это цифра, возвращаем выражение без аргументов return Expression(token)
if (token == "(") { auto result = parse() if (parse_token() != ")") throw std::runtime_error("Expected ')'") return result // Если это скобки, парсим и возвращаем выражение в скобках }
// Иначе, это унарная операция ("-", "sin", и т.п.) auto arg = parse_simple_expression() // Парсим ее аргумент. return Expression(token, arg) }
И наконец, последняя и самая сложная часть - бинарные выражения. У бинарных операций есть приоритеты, например у + и - приоритет меньше чем у * и /, у ** (возведение в степень) приоритет больше чем у умножения. Напишем функцию, возвращающую приоритет бинарной операции:
int get_priority(const std::string& token) { if (token == "+") return 1 if (token == "-") return 1 if (token == "*") return 2 if (token == "/") return 2 if (token == "mod") return 2 // остаток от деления if (token == "**") return 3 // степень return 0 // Возвращаем 0 если токен - это не бинарная операция (например ")") }
Парсер бинарных выражений разбирает выражение в цикле, начиная с левой стороны. Выражение слева - это либо простое выражение, либо бинарное выражение, полученное на предыдущей итерации. Выражение справа получается рекурсивным вызовом парсера, при этом бинарные операции справа должны иметь больший приоритет чем текущая операция.
Expression Parser::parse_binary_expression(int min_priority) { auto left_expr = parse_simple_expression() // Парсим простое выражение.
for ( ) { auto op = parse_token() // Пробуем парсить бинарную операцию. auto priority = get_priority(op) // Выходим из цикла если ее приоритет слишком низок (или это не бинарная операция). if (priority <= min_priority) { input -= op.size() // Отдаем токен обратно, return left_expr // возвращаем выражение слева. }<br> // Парсим выражение справа. Текущая операция задает минимальный приоритет. auto right_expr = parse_binary_expression(priority) left_expr = Expression(op, left_expr, right_expr) // Обновляем выражение слева. } // Повторяем цикл: парсинг операции, и проверка ее приоритета. }
Функция parse() просто вызывает парсер бинарных выражений, передавая ему нулевой минимальный приоритет операций (любая бинарная операция):
Expression Parser::parse() { return parse_binary_expression(0) }
Для строки"3*4/5" код работает так:
Сначала left_expr парсится как простое выражение "3", затем парсится токен "*", его приоритет (2) больше минимального (0). Парсится выражение справа: делается вызов parse_binary_expression(2). Здесь input="4/5", left_expr парсится как "4", за ним идет токен с операцией "/", но теперь его приоритет 2 не больше минимального (2), цикл сразу же заканчивается, токен "/" возвращается обратно (input="/5"), возвращается выражение "4". Из правых и левых частей получается выражение ("*", "3", "4"), цикл повторяется. Опять парсится токен "/", его приоритет (2) больше минимального (0). Парсится выражение справа: вызов parse_binary_expression(2), при этом input = "5". left_expr парсится как "5", за ним идет пустой токен "" (конец строки). приоритет 0 меньше минимального (2), возвращается выражение "5". Из правых и левых частей получается выражение ("/", ("*", "3", "4"), "5"). Цикл повторяется, опять парсится пустой токен "", функция завершается.
Если приоритеты повышаются, например 2+3*4/5, то во вложенных вызовах parse_binary_expression успевает отработать дольше:
Парсится выражение слева "2" и операция "+" (приоритет 1). Для правой части делается вызов parse_binary_expression(1). Здесь всё как в предыдущем примере, input="3*4/5", только минимальный приоритет равен 1 а не 0. Цикл проходит несколько итераций, и мы получаем ("/", ("*", "3", "4"), "5") Дальше идут только пустые токены, т.к. input закончился. Выходим из цикла. Объединяем правую и левую части, получаем ("+", "2", ("/", ("*", "3", "4"), "5")).
Итак, у нас есть парсер. Но надо еще как-то вычислять результаты парсинга. Это можно сделать одной функцией:
double eval(const Expression& e) { switch (e.args.size()) { case 2: { // Два аргумента - бинарные операции. auto a = eval(e.args[0]) auto b = eval(e.args[1]) if (e.token == "+") return a + b if (e.token == "-") return a - b if (e.token == "*") return a * b if (e.token == "/") return a / b if (e.token == "**") return pow(a, b) if (e.token == "mod") return (int)a % (int)b throw std::runtime_error("Unknown binary operator") }
case 1: { // Один аргумент. auto a = eval(e.args[0]) if (e.token == "+") return +a if (e.token == "-") return -a if (e.token == "abs") return abs(a) if (e.token == "sin") return sin(a) if (e.token == "cos") return cos(a) throw std::runtime_error("Unknown unary operator") }
case 0: { // Числа (ноль аргументов). return strtod(e.token.c_str(), nullptr) } }
throw std::runtime_error("Unknown expression type") }
>>> Здесь <<< можно найти весь код целиком.<br>
Что делать если надо добавить функцию, которая принимает больше одного аргумента? - Функция, принимающая несколько аргументов - это функция принимающая один аргумент-кортеж (список). По этому самое простое решение - это ввести бинарную операцию "," (запятая), которая будет делать кортеж (список) чисел.
