6
\$\begingroup\$

I am fairly new to C++ and I was wondering if there is anything I can improve in this code(perf, readability)? Thanks. This is the full code: Github Link

I will post the parser that creates a rpn representation of an input string and a function that evaluates the rpn here(the rest is on the 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 parentheses\n";
        }
        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());
}
\$\endgroup\$
6
  • \$\begingroup\$ Elaborate in what way? \$\endgroup\$ Apr 2, 2021 at 17:33
  • 1
    \$\begingroup\$ Welcome to CodeReview! Because we like to have things stand alone (in case the target of a link changes or disappears at some point in the future), the question needs a bit more context to allow a review to be done on just this code. So for instance, a bit of description of what tokenize returns and some examples of the kinds of equations you're intending to parse would be helpful. \$\endgroup\$
    – Edward
    Apr 2, 2021 at 19:08
  • \$\begingroup\$ I will post most of the functions here, I was just concerned that it would be too long of a post. How much should I include in the post? \$\endgroup\$ Apr 2, 2021 at 19:40
  • \$\begingroup\$ Unlike some other sister sites, we tend to like more complete code. Reviews tend to benefit from a fuller context; it makes the code easier to meaningfully review and it gives the person asking for the review a more useful result. You don't need to post everything, but if it fits, it's probably not too long. \$\endgroup\$
    – Edward
    Apr 2, 2021 at 19:45
  • \$\begingroup\$ Ok I edited it to include everything other than the rendering for the graphing calculator. Thanks \$\endgroup\$ Apr 2, 2021 at 19:51

2 Answers 2

5
\$\begingroup\$

In all, it's not bad, especially for someone new to the language. Here are some things that may help you improve your code.

Know the difference betwee <cmath> and <math.h>

The difference between the two forms is that the former defines things within the std:: namespace versus into the global namespace. This means that in your unary_func_tbl, each of the functions should be prefixed with std::. Also, if we just write std::sin we don't need to further qualify it with & since we are referring to the function rather than actually calling it.

Simplify your regex string using a raw string

Regex expressions are complex enough without the added complexity of having to also escape backslash characters. We can use a raw string for this:

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]+|[\\-\\+\\\\\(\\)\\/\\*\\^\\]")"};

Fix your regex

When I made the change I suggested above, it was easier to spot that there was a spurious extra '\' character before the penultimate ')' character. There are still some issues that might be improved here. I'll come back to the keyword portion of the regex later, but wanted to take a closer look at the other clauses. First, we have ^- which matches exactly a single - at the beginning of the string. I assume it's captured that way to take care of unary minus, but I believe the last clause captures that, so it could be removed. Moving on to the next clause, it is:

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

This is not a very efficient or clear construction. What it seeks to capture is either integers with no decimal point or numbers with decimal point. It also requires at least one digit after the decimal point. The much more straightforward way to do that is like this:

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

Finally, the last curious clause was originally this:

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

I don't think that does what you want. It's hard to tell by peering through that "picket fence" but I think what you intend looks more like this:

[-+\()/*^]

Within bracket expressions, those other characters lose their special meaning, just in the way that '[.]' matches a period instead of any-character, which it would outside the [] context. Regular expressions are complex enough without adding extra characters!

Simplify your code

The code has a number of places in which somthing like this is done:

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

This is much more easily and simply written as return id == 0;

Don't Repeat Yourself (DRY)

The code enumerates the function names at least three times. There is the unary_func_tbl, the funcs set and once in the regex. This leads to errors, such as the fact that "asin" appears twice within funcs and trunc is omitted from the regex. There are many ways to combine these, but since you're using C++20, I'll show you how to use a new feature from that version of the standard. The next few suggestions show how that might be done.

Use contains

The current version of is_func is like this:

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

As mentioned above, this can be simplified:

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

But we don't actually need the separate funcs because we can simply use unary_func_tbl:

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

Note that contains for a std::unordered_set was introduced in C++20, so your compiler may or not implement that. If it does, however, it means that you can simply omit funcs entirely. A similar thing can be done with is_binary_op.

Construct the regex

Since the function names are already in func_names, we can extract them into an appropriate regex using this:

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();
}

This uses the C++20 std::views::keys. There may be an even more efficient way to construct the string as as constexpr function, but I didn't look into it very deeply. The nice part about this, however, is that we can use it like this:

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

Use/omit parentheses to clarify

The code currently contains this rather complex construct:

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() != "("))

First, the trailing backslashes are not required in C++ (except in the context of multiline macros, which you also should generally not be using in C++). Second, because && has a higher precedence than || the way this expression is evaluated requires the reader of the code to remember this fact in order to correctly understand what it's doing. Adding parentheses around subexpressions won't affect the compiler but it will give the reader more confidence in both understanding the code and in realizing that the original programmer (you!) intended it to be that way. The extra parentheses around get_prec(tok) however, confuses things and elicits doubt and should be eliminated.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used.

\$\endgroup\$
5
\$\begingroup\$

Avoid overly large indentation

I can't read the contents of the maps and set being declared at the start of the code without scrolling far to the right. I suggest you reduce the indentation by putting the first element inside the initializer list on its own line, like so:

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)}
};

Use initializer lists instead of std::make_pair() where possible

In the case of the above map, the compiler knows up front what the type of the value of each element is, so you don't have to use std::make_pair(). You should be able to write:

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

Use an enum class for the associativity

To increase type safety and to allow the compiler to catch more errors, make the associativity an enum class, like so:

enum class associativity {
    LEFT,
    RIGHT
};

And then use it like so:

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

Use fabs() instead of abs()

There is a compile error, since you wrote &abs in the initialization of unary_func_tbl, which should have been &fabs. Note that the ampersands here are redundant, you can omit them.

You could also have written std::abs, and it would have been fine, since that one has an overload for doubles.

No need for funcs

The set funcs is not necessary, you already have unary_func_tbl which contains the same information.

Redundant if-statements

An if-statement that looks like:

if (condition) return true; else return false;

Is redundant. You can just write:

return condition;

For example, is_left_assoc() can be rewritten as:

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

Use contains() instead of count()

Since you added the C++20 tag, you should know that they finally added the contains() member function to the associative containers in the STL. So now you can write:

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

About error handling

There are a few things where your error handling could be improved. First, write error messages to std::cerr. This ensures they don't get mixed with the normal output, in particular consider that someone might call your program and redirect the standard output to a file.

Second, use a consistent way to handle errors. Most errors in the input are just ignored, some get error messages (mismatched parentheses), some error handling is in the wrong place (compute_binary_ops() checks for invalid operators, but this should never happen there since it had to pass is_binary_op() first), and only in one place do you actually stop parsing by calling exit(-1).

I suggest that you start using exceptions to report errors. Create one or more exception types that derive from one of the standard exception types, I recommend either std::exception or std::runtime_error. For example:

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) {}
};

And then throw whenever you encounter an error:

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

If you don't catch exceptions, this will ensure your program aborts with a non-zero exit code, and it will print the error message. It also allows callers to catch exceptions in case they are able to handle them in some useful way.

Don't forget to throw an exception in all unhandled cases, for example add the following to the end of the if-else chain in s_yard():

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

Consider using a parser generator

The main goal of your program is plotting equations. Parsing equations is just something to do to reach that goal. Consider using a parser generator that will generate the C++ code for you to parse equations. Some well known tools for generating C++ parsers are GNU Flex and GNU Bison (used together), although there are many others.

Performance

It looks like when you will be plotting an equation, you will call eval_rpn() many times. Even though you only have to tokenize and call s_yard() once, your code still has to parse each individual token to find out if they are a value, function, or binary operator. Wouldn't it be nice if we could pre-process it even more, so that we don't have to do that each time we want to evaluate the equation?

Ideally, we want to generate a function that we can call with the variable's value as an argument, and that returns the result of applying the equation. Thanks to lambdas and std::function objects, we can actually make a poor man's JIT compiler in C++. Here is an example of what it looks like:

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();
}

And you use it like so:

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';

If you want to go even faster than this, you could consider converting the equation to C++ source code and compiling it into a shared library, and use dlopen() to load it.

Since you are using SDL to plot the equation, you could also consider generating a compute shader from the equation, and letting the GPU process it.

\$\endgroup\$
7
  • \$\begingroup\$ Can you please elaborate on the performance section? I don't understand why the lambda would operate on the whole stack. Also how would the lambda be created with the plus operator or the sin function(any func)? \$\endgroup\$ Apr 2, 2021 at 22:56
  • 1
    \$\begingroup\$ I changed it so it no longer needs the stack at the end, the "poor man's JIT" now produces a single std::function that you can use to evaluate the equation for any value of the variable. I added a fully working example. Let me know if things are still unclear. \$\endgroup\$
    – G. Sliepen
    Apr 3, 2021 at 8:40
  • \$\begingroup\$ I was told that the map of function pointers is not compliant because it is taking the address of standard library functions. Should I replace this with a if else chain to compute the unary functions? \$\endgroup\$ Apr 3, 2021 at 15:49
  • 1
    \$\begingroup\$ I don't see anything wrong with the map of function pointers. It's perfectly fine to take the address of a function, regardless of where it comes from. \$\endgroup\$
    – G. Sliepen
    Apr 3, 2021 at 15:55
  • \$\begingroup\$ ok, and btw the perf suggestion you made worked very well. thanks \$\endgroup\$ Apr 3, 2021 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.