Программа на C ++ для построения уравнения

Я новичок в C ++, и мне было интересно, можно ли что-нибудь улучшить в этом коде (производительность, удобочитаемость)? Спасибо. Это полный код: Ссылка на Github

Я опубликую парсер, который создает rpn-представление входной строки и функцию, которая оценивает rpn здесь (остальное находится на github):

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string_view>
#include <string>
#include <vector>
#include <utility>
#include <stack>
#include <numbers>
#include <regex>
#include <variant>
#include <chrono>
#include <cmath>

constexpr int LEFT_ASSOC = 0;
constexpr int RIGHT_ASSOC = 1;

//pair is <prec, assoc_id>
static const std::unordered_map<std::string_view, std::pair<int, int>> assoc_prec{ {"^", std::make_pair(4, RIGHT_ASSOC)},
                                                                                   {"*", std::make_pair(3, LEFT_ASSOC)},
                                                                                   {"/", std::make_pair(3, LEFT_ASSOC)},
                                                                                   {"+", std::make_pair(2, LEFT_ASSOC)},
                                                                                   {"-", std::make_pair(2, LEFT_ASSOC)} };

static const std::unordered_map<std::string_view, double(*)(double)> unary_func_tbl{ {"sin", &sin},
                                                                                     {"cos", &cos},
                                                                                     {"sqrt", &sqrt},
                                                                                     {"abs", &abs},
                                                                                     {"tan", &tan},
                                                                                     {"acos", &acos},
                                                                                     {"asin", &asin},
                                                                                     {"atan", &atan},
                                                                                     {"log", &log},
                                                                                     {"log10", &log10},
                                                                                     {"cosh", &cosh},
                                                                                     {"sinh", &sinh},
                                                                                     {"tanh", &tanh},
                                                                                     {"exp", &exp},
                                                                                     {"cbrt", &cbrt},
                                                                                     {"tgamma", &tgamma},
                                                                                     {"lgamma", &lgamma},
                                                                                     {"ceil", &ceil},
                                                                                     {"floor", &floor},
                                                                                     {"acosh", &acosh},
                                                                                     {"asinh", &asinh},
                                                                                     {"trunc", &trunc},
                                                                                     {"atanh", &atanh} };

static const std::unordered_set<std::string_view> funcs{ "sin", "tan", "acos", "asin", "asin", "abs",
                                                         "atan", "cosh", "sinh", "cos", "tanh",
                                                         "acosh", "asinh", "atanh", "exp", "ldexp",
                                                         "log", "log10", "sqrt", "cbrt", "tgamma",
                                                         "lgamma", "ceil", "floor", "trunc" };

bool is_left_assoc(std::string_view str)
{
    int id = assoc_prec.at(str).second;
    if (id == 0) return true;
    else return false;
}

bool is_binary_op(std::string_view str)
{
    if (str == "/" || str == "*" || str == "+" || str == "-" || str == "^")
    {
        return true;
    }
    else return false;
}

bool is_func(std::string_view str)
{
    if (funcs.count(str) > 0) return true;
    else return false;
}


//handls decimal numbers
bool is_num(std::string_view str)
{
    int num_found_periods = 0;
    for (const auto c : str)
    {
        if (c == '.')
        {
            num_found_periods++;
            if (num_found_periods > 1)
            {
                return false;
            }
        }
        if (!isdigit(c) && c != '.')
        {
            return false;
        }
    }
    return true;
}

int get_prec(std::string_view str)
{
    if (is_func(str))
    {
        return 1; //TODO: check it this is the correct value
    }
    else if (is_binary_op(str))
    {
        return assoc_prec.at(str).first;
    }
    else
    {
        return 0;
    }
}


//from https://stackoverflow.com/a/56204256
//modified regex expr
std::vector<std::string> tokenize(const std::string& str)
{
    std::vector<std::string> res;
    const std::regex words_regex("(sin|tan|acos|asin|abs|atan|cosh|sinh|cos|"
                                 "tanh|acosh|asinh|atanh|exp|ldexp|log|log10|"
                                 "sqrt|cbrt|tgamma|lgamma|ceil|floor|x|e)|^-|[0-9]?"
                                 "([0-9]*[.])?[0-9]+|[\-\+\\(\)\/\*\^\]",
                                  std::regex_constants::egrep);

    auto words_begin = std::sregex_iterator(str.begin(), str.end(), words_regex);
    auto words_end = std::sregex_iterator();
    for (std::sregex_iterator i = words_begin; i != words_end; ++i) 
    {
        res.push_back((*i).str());
    }
    return res;
}

//params: 
//str - string to be converted
//var_name - any occurances of this as a seperate token will be treated as a varable
//convert string in infix notation to a string in Reverse Polish Notation
//using dijkstra's shunting yard algorithm 
std::vector<std::variant<double, std::string>> s_yard(const std::string& str, std::string var_name)
{
    std::vector<std::variant<double, std::string>> output_queue;
    std::stack<std::string> op_stack;

    for (const auto& tok : tokenize(str))
    {
        if (tok == "pi")
        {
            output_queue.push_back(std::numbers::pi_v<double>);
        }
        else if (tok == "e")
        {
            output_queue.push_back(std::numbers::e_v<double>);
        }
        else if (tok == var_name)
        {
            output_queue.push_back(tok);
        }
        else if (is_num(tok))
        {
            output_queue.push_back(strtod(tok.c_str(), NULL));
        }
        else if (is_func(tok))
        {
            op_stack.push(tok);
        }
        else if (is_binary_op(tok))
        {   
            while (!op_stack.empty() && 
                  (is_binary_op(op_stack.top()) && get_prec(op_stack.top()) > (get_prec(tok)) || 
                  (get_prec(op_stack.top()) == get_prec(tok) && is_left_assoc(tok))) && 
                  (op_stack.top() != "("))
            {
                //pop operators from stack to queue
                while (!op_stack.empty())
                {
                    output_queue.push_back(op_stack.top());
                    op_stack.pop();
                }
            }
            op_stack.push(tok);
        }
        else if (tok == "(")
        {
            op_stack.push(tok);
        }
        else if (tok == ")")
        {
            while (op_stack.top() != "(")
            {
                output_queue.push_back(op_stack.top());
                op_stack.pop();
            }
            if (op_stack.top() == "(")
            {
                op_stack.pop();
            }
            if (is_func(op_stack.top()))
            {
                output_queue.push_back(op_stack.top());
                op_stack.pop();
            }
        }
    }
    //all tokens read
    while (!op_stack.empty())
    {
        //there are mismatched parentheses
        if (op_stack.top() == "(" || op_stack.top() == ")")
        {
            std::cout << "mismatched parenthesesn";
        }
        output_queue.push_back(op_stack.top());
        op_stack.pop();
    }
    return output_queue;
}

double compute_binary_ops(double d1, double d2, std::string_view op)
{
    if (op == "*") return d1 * d2;
    else if (op == "+") return d1 + d2;
    else if (op == "-") return d1 - d2;
    else if (op == "/") return d1 / d2;
    else if (op == "^") return pow(d1, d2);
    else
    {
        std::cout << R"(invalid operator: ")" << op << R"("  passed to func "compute_binary_ops")" << 'n';
        exit(-1);
    }
}

double eval_rpn(const std::vector<std::variant<double, std::string>>& tokens, std::string var_name, double var_value)
{   
    double d2 = 0.0;
    double res = 0.0;
    std::stack<std::variant<double, std::string>> stack;
    for (const auto& tok : tokens)
    {
        if (const double *number = std::get_if<double>(&tok))
        {
            stack.push(*number);
        }
        else if (std::get<std::string>(tok) == var_name)
        {
            stack.push(var_value);
        }
        //handle binary operaters
        else if(is_binary_op(std::get<std::string>(tok)))
        {
            d2 = std::get<double>(stack.top());
            stack.pop();
            if (!stack.empty())
            {       
                const double d1 = std::get<double>(stack.top());
                stack.pop();
                res = compute_binary_ops(d1, d2, std::get<std::string>(tok));
                stack.push(res);
            }
            else
            {
                if (std::get<std::string>(tok) == "-") res = -(d2);
                else res = d2;
                stack.push(res);
            }
        }
        //handle funcs(unary ops)
        else if (is_func(std::get<std::string>(tok)))
        {
            if (!stack.empty())
            {
                const double d1 = std::get<double>(stack.top());
                stack.pop();
                res = (*unary_func_tbl.at(std::get<std::string>(tok)))(d1);
                stack.push(res);
            }
            else
            {
                if (std::get<std::string>(tok) == "-") res = -(d2);
                else res = d2;
                stack.push(res);
            }
        }
    }
    return std::get<double>(stack.top());
}

2 ответа
2

В целом неплохо, особенно для новичка в языке. Вот некоторые вещи, которые могут помочь вам улучшить ваш код.

Знай разницу между <cmath> и <math.h>

Разница между двумя формами состоит в том, что первая определяет вещи внутри std:: пространство имен по сравнению с глобальным пространством имен. Это означает, что в вашем unary_func_tbl, каждая функция должна иметь префикс std::. Кроме того, если мы просто напишем std::sin нам не нужно уточнять это с помощью & поскольку мы говорим о функции, а не вызываем ее.

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

Выражения регулярных выражений достаточно сложны без дополнительной сложности, связанной с необходимостью экранирования символов обратной косой черты. Мы можем использовать необработанная строка для этого:

const std::regex words_regex(R"((sin|tan|acos|asin|abs|atan|cosh|sinh|cos|)"
                R"(tanh|acosh|asinh|atanh|exp|ldexp|log|log10|)"
                R"(sqrt|cbrt|tgamma|lgamma|ceil|floor|x|e)|^-|[0-9]?)"
                R"(([0-9]*[.])?[0-9]+|[\-\+\\(\)\/\*\^\]")"};

Исправьте свое регулярное выражение

Когда я внес предложенное выше изменение, было легче обнаружить ложное лишнее '' символ перед предпоследним ')' символ. Есть еще некоторые проблемы, которые здесь можно исправить. Я вернусь к ключевой части регулярного выражения позже, но хотел бы более подробно рассмотреть другие предложения. Во-первых, у нас есть ^- что соответствует ровно одному - в начале строки. Я предполагаю, что это фиксируется таким образом, чтобы позаботиться об унарном минусе, но я считаю, что последнее предложение фиксирует это, поэтому его можно удалить. Переходя к следующему пункту, это:

[0-9]?([0-9]*[.])?[0-9]+

Это не очень эффективная или понятная конструкция. Он пытается захватить либо целые числа без десятичной точки, либо числа с десятичной точкой. Также требуется, чтобы после десятичной точки была как минимум одна цифра. Более простой способ сделать это:

([0-9]+[.])?[0-9]+

Наконец, последняя любопытная фраза изначально была такой:

[\-\+\\(\)\/\*\^\]

Я не думаю, что это то, что вы хотите. Трудно сказать, глядя сквозь это “забор” но я думаю, что то, что вы собираетесь делать, выглядит примерно так:

[-+()/*^]

В пределах выражения в скобках, эти другие символы теряют свое особое значение точно так же, как '[.]' соответствует точке вместо любой персонаж, что было бы за пределами [] контекст. Регулярные выражения достаточно сложны без добавления лишних символов!

Упростите свой код

В коде есть несколько мест, в которых делается что-то вроде этого:

if (id == 0) return true;
else return false;

Это намного проще и проще записать как return id == 0;

Не повторяйся (СУХОЙ)

Код перечисляет имена функций не менее трех раз. Здесь unary_func_tbl, то funcs set и один раз в регулярном выражении. Это приводит к ошибкам, например к тому, что “asin” дважды появляется в funcs и trunc опускается в регулярном выражении. Есть много способов их комбинировать, но, поскольку вы используете C ++ 20, я покажу вам, как использовать новую функцию из этой версии стандарта. Следующие несколько предложений показывают, как это можно сделать.

Использовать contains

Текущая версия is_func вот так:

bool is_func(std::string_view str)
{
    if (funcs.count(str) > 0) return true;
    else return false;
}

Как упоминалось выше, это можно упростить:

bool is_func(std::string_view str) {
    return funcs.count(str) > 0;
}

Но на самом деле нам не нужен отдельный funcs потому что мы можем просто использовать unary_func_tbl:

bool is_func(std::string_view str) {
    return unary_func_tbl.contains(str);
}

Обратите внимание, что contains для std::unordered_set был представлен в C ++ 20, поэтому ваш компилятор может это реализовать или не реализовать. Однако если это так, это означает, что вы можете просто опустить funcs полностью. То же самое можно сделать с is_binary_op.

Создайте регулярное выражение

Поскольку имена функций уже есть в func_names, мы можем извлечь их в соответствующее регулярное выражение, используя это:

static const std::string func_name_regex() {
    auto func_names{std::views::keys(unary_func_tbl)};
    std::ostringstream os;
    os << "(";
    for (const auto &name : std::views::keys(unary_func_tbl)) {
        os << name << "|";
    }
    os << R"(x|e)|)"
        << R"(([0-9]+[.])?[0-9]+|[-+()/*^])";
    return os.str();
}

Это использует C ++ 20 std::views::keys. Может быть еще более эффективный способ построить строку как constexpr функции, но я не очень глубоко в нее разбирался. Однако приятным моментом в этом является то, что мы можем использовать это так:

static const std::regex words_regex(func_name_regex(),
                              std::regex_constants::egrep);

Используйте / опускайте круглые скобки для пояснения

В настоящий момент код содержит эту довольно сложную конструкцию:

while (!op_stack.empty() && 
      (is_binary_op(op_stack.top()) && get_prec(op_stack.top()) > (get_prec(tok)) || 
      (get_prec(op_stack.top()) == get_prec(tok) && is_left_assoc(tok))) && 
      (op_stack.top() != "("))

Во-первых, завершающие обратные косые черты не требуются в C ++ (за исключением контекста многострочных макросов, которые вам также обычно не следует использовать в C ++). Во-вторых, потому что && имеет более высокий приоритет, чем || способ вычисления этого выражения требует, чтобы читатель кода запомнил этот факт, чтобы правильно понять, что он делает. Добавление круглых скобок вокруг подвыражений не повлияет на компилятор, но даст читателю больше уверенности как в понимании кода, так и в понимании того, что исходный программист (вы!) Так и задумал. Дополнительные круглые скобки вокруг get_prec(tok) тем не менее, это сбивает с толку и вызывает сомнения, и от него следует отказаться.

Предоставьте полный код рецензентам

Это не столько изменение кода, сколько изменение того, как вы представляете его другим людям. Без полного контекста кода и примера того, как его использовать, другим людям потребуется больше усилий, чтобы понять ваш код. Это влияет не только на проверку кода, но и на его обслуживание в будущем вами или другими лицами. Один из хороших способов решить эту проблему – использовать комментарии. Еще один хороший метод – включить тестовый код, показывающий, как ваш код будет использоваться.

    Избегайте слишком большого отступа

    Я не могу прочитать содержимое карт и набора, объявленного в начале кода, без прокрутки вправо. Я предлагаю вам уменьшить отступ, поместив первый элемент внутри списка инициализаторов в отдельной строке, например:

    static const std::unordered_map<std::string_view, std::pair<int, int>> assoc_prec{
        {"^", std::make_pair(4, RIGHT_ASSOC)},
        {"*", std::make_pair(3, LEFT_ASSOC)},
        {"/", std::make_pair(3, LEFT_ASSOC)},
        {"+", std::make_pair(2, LEFT_ASSOC)},
        {"-", std::make_pair(2, LEFT_ASSOC)}
    };
    

    Используйте списки инициализаторов вместо std::make_pair() где возможно

    В случае приведенной выше карты компилятор заранее знает, каков тип значения каждого элемента, поэтому вам не нужно использовать std::make_pair(). Вы должны уметь писать:

    static const std::unordered_map<std::string_view, std::pair<int, int>> assoc_prec{
        {"^", {4, RIGHT_ASSOC}},
        {"*", {3, LEFT_ASSOC}},
        ...
    

    Используйте enum class за ассоциативность

    Чтобы повысить безопасность типов и позволить компилятору перехватывать больше ошибок, сделайте ассоциативность enum class, вот так:

    enum class associativity {
        LEFT,
        RIGHT
    };
    

    А потом используйте это так:

    static const std::unordered_map<std::string_view, std::pair<int, associativity>> assoc_prec{
        {"^", {4, associativity::RIGHT}},
        {"*", {3, associativity::LEFT}},
        ...
    };
    

    Использовать fabs() вместо abs()

    Ошибка компиляции, поскольку вы написали &abs при инициализации unary_func_tbl, который должен был быть &fabs. Обратите внимание, что амперсанды здесь избыточны, вы можете их опустить.

    Вы также могли бы написать std::abs, и это было бы хорошо, так как у этого есть перегрузка для doubleс.

    Нет необходимости в funcs

    Набор funcs не нужно, у вас уже есть unary_func_tbl который содержит ту же информацию.

    Избыточный if-заявления

    An if-выражение, которое выглядит так:

    if (condition) return true; else return false;
    

    Избыточен. Вы можете просто написать:

    return condition;
    

    Например, is_left_assoc() можно переписать как:

    bool is_left_assoc(std::string_view str)
    {
        return assoc_prec[str].second == associativity::LEFT;
    }
    

    Использовать contains() вместо count()

    Поскольку вы добавили тег C ++ 20, вы должны знать, что они наконец добавили contains() функция-член ассоциативных контейнеров в STL. Итак, теперь вы можете написать:

    bool is_func(std::string_view str)
    {
        return funcs.contains(str);
    }
    

    Об обработке ошибок

    Есть несколько вещей, в которых можно улучшить обработку ошибок. Сначала напишите сообщения об ошибках в std::cerr. Это гарантирует, что они не смешиваются с обычным выводом, в частности, учтите, что кто-то может вызвать вашу программу и перенаправить стандартный вывод в файл.

    Во-вторых, используйте последовательный способ обработки ошибок. Большинство ошибок во входных данных просто игнорируются, некоторые получают сообщения об ошибках (несоответствующие скобки), некоторая обработка ошибок выполняется не в том месте (compute_binary_ops() проверяет недопустимые операторы, но этого никогда не должно происходить, так как он должен был пройти is_binary_op() first), и только в одном месте вы фактически прекращаете синтаксический анализ, вызывая exit(-1).

    Я предлагаю вам начать использовать исключения для сообщения об ошибках. Создайте один или несколько типов исключений, которые являются производными от одного из стандартные типы исключенийЯ рекомендую либо std::exception или же std::runtime_error. Например:

    class parse_error: public std::runtime_error {
    public:
         explicit parse_error(const string &what): std::runtime_error(what) {}
         explicit parse_error(const char *what): std::runtime_error(what) {}
    };
    

    А потом throw всякий раз, когда вы сталкиваетесь с ошибкой:

    if (op_stack.top() == "(" || op_stack.top() == ")")
    {
        throw parse_error("Mismatched parentheses");
    }
    

    Если вы не поймаете исключения, это обеспечит прерывание вашей программы с ненулевым кодом выхода и напечатает сообщение об ошибке. Это также позволяет вызывающим абонентам перехватывать исключения, если они могут обработать их каким-либо полезным способом.

    Не забывайте генерировать исключение во всех необработанных случаях, например, добавьте следующее в конец ifelse цепь в s_yard():

    else
    {
        throw parse_error("Unknown token: " + tok);
    }
    

    Рассмотрите возможность использования генератора парсеров

    Основная цель вашей программы – построение уравнений. Анализ уравнений – это просто то, что нужно сделать для достижения этой цели. Рассмотрите возможность использования генератор парсеров который сгенерирует код C ++ для анализа уравнений. Некоторые хорошо известные инструменты для генерации синтаксических анализаторов C ++: GNU Flex и GNU Bison (используются вместе), хотя есть многие другие.

    Представление

    Похоже, когда вы будете строить уравнение, вы вызовете eval_rpn() много раз. Хотя вам нужно только токенизировать и звонить s_yard() однажды ваш код все равно должен проанализировать каждый отдельный токен, чтобы выяснить, являются ли они значением, функцией или бинарным оператором. Разве не было бы неплохо, если бы мы могли предварительно обработать его еще больше, чтобы нам не приходилось делать это каждый раз, когда мы хотим оценить уравнение?

    В идеале мы хотим сгенерировать функцию, которую мы можем вызвать со значением переменной в качестве аргумента и которая возвращает результат применения уравнения. Благодаря лямбдам и std::function объектов, мы действительно можем сделать JIT-компилятор для бедняков на C ++. Вот пример того, как это выглядит:

    std::function<double(double)> build_function(const std::vector<std::variant<double, std::string>>& tokens, std::string var_name)
    {   
        std::stack<std::function<double(double)>> stack;
    
        for (const auto& tok : tokens)
        {
            if (const double *num_ptr = std::get_if<double>(&tok))
            {
                stack.push([number=*num_ptr](double){return number;});
            }
            else if (std::get<std::string>(tok) == var_name)
            {
                stack.push([](double var_value){return var_value;});
            }
            else if(is_binary_op(std::get<std::string>(tok)))
            {
                auto right = stack.top();
                stack.pop();
                auto left = stack.top();
                stack.pop();
                auto op = std::get<std::string>(tok);
                stack.push([left, right, op](double var_value){return compute_binary_ops(left(var_value), right(var_value), op);});
            }
            else if (is_func(std::get<std::string>(tok)))
            {
                auto operand = stack.top();
                stack.pop();
                auto function = unary_func_tbl.at(std::get<std::string>(tok));
                stack.push([operand, function](double var_value){return function(operand(var_value));});
            }
        }
    
        return stack.top();
    }
    

    И вы используете это так:

    auto rpn = s_yard("sin(x) + 1", "x");
    auto function = build_function(rpn, "x");
    
    for(double x = 0; x <= 6.28; x += 0.1)
        std::cout << x << ' ' << func(x) << 'n';
    

    Если вы хотите пойти еще быстрее, вы можете преобразовать уравнение в исходный код C ++ и скомпилировать его в общую библиотеку и использовать dlopen() чтобы загрузить это.

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

    • Не могли бы вы подробнее рассказать о разделе производительности? Я не понимаю, почему лямбда работает со всем стеком. Также как можно было бы создать лямбда с помощью оператора плюса или функции sin (любой функции)?

      – expr_champ2

    • Я изменил его так, чтобы он больше не нуждался в стеке в конце, “JIT для бедняков” теперь производит единственный std::function который можно использовать для вычисления уравнения для любого значения переменной. Я добавил полностью рабочий пример. Дайте мне знать, если что-то по-прежнему неясно.

      – Г. Сон

    • Мне сказали, что карта указателей функций несовместима, потому что она принимает адрес стандартных библиотечных функций. Должен ли я заменить это цепочкой if else для вычисления унарных функций?

      – expr_champ2

    • 1

      Я не вижу ничего плохого в карте указателей функций. Совершенно нормально взять адрес функции, независимо от того, откуда он.

      – Г. Сон

    • хорошо, и, кстати, предложение о перфомансе, которое вы сделали, сработало очень хорошо. Благодарность

      – expr_champ2

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *