11
\$\begingroup\$

I hesitated quite a bit of time before posting this question since the code to review is more or less a monster (with regards to its size). It is a basic mathematical expressions evaluator, but with one interesting additional feature: you can register callbacks that can be used in the expression to evaluate. First of all, here is a little example of how it works (taken straight from the documentation):

evaluator<int> eval;

std::cout << eval("2 + 5 * 3") << '\n'; // 17
std::cout << eval("(4 + 2) * (2 ** 3)") << '\n'; // 48
std::cout << eval("5!") << '\n'; // 120

// Connect the absolute value function
eval.connect("abs", [](int n) {
    return std::abs(n);
});

std::cout << eval("2 * abs(2 - 8) + 4") << '\n'; // 16

If it makes you feel better, you might want to consider this question to be a late answer to the April 2015 Community Challenge since this is what motivated me to update my old evaluator in the first place :)

The evaluator

So, first things first: the code revolves around an evaluator object. This object has the ability to connect and disconnect callbacks and to evaluate mathematical expressions with either the method evaluate or operator() so that it can also be used as a function object. Here is the evaluator class. Note that for the purpose of the question, the body of the functions is embedded in the classes but in the real code, the implementation is in a separate .inl/.cpp file:

template<typename Number>
class evaluator
{
    public:

        /**
         * @brief Evaluate a mathematical expression.
         */
        auto evaluate(const std::string& expression) const
            -> Number
        {
            auto tokens = tokenize<Number>(expression);
            return eval_postfix(to_postfix(tokens));
        }

        /**
         * @brief Calls evaluate.
         */
        auto operator()(const std::string& expression) const
            -> Number
        {
            return evaluate(expression);
        }

        /**
         * @brief Register a function.
         *
         * Register a function that will be called when the given
         * name is used in the mathematical expression.
         */
        template<typename Func>
        auto connect(const std::string& name, Func&& function)
            -> void
        {
            callbacks.emplace(
                std::piecewise_construct,
                std::forward_as_tuple(name),
                std::forward_as_tuple(function)
            );
        }

        /**
         * @brief Unregister a connected function.
         */
        auto disconnect(const std::string& name)
            -> void
        {
            callbacks.erase(name);
        }

    private:

        auto eval_postfix(std::stack<token<Number>>&& tokens) const
            -> Number
        {
            std::stack<Number> operands;

            while (not tokens.empty())
            {
                token<Number> tok = tokens.top();
                tokens.pop();

                switch (tok.type)
                {
                    case token_t::operand:
                    {
                        operands.push(tok.data);
                        break;
                    }

                    case token_t::name:
                    {
                        auto&& func = callbacks.at(tok.name);

                        if (operands.size() < func.arity)
                        {
                            throw error(std::string("not enough operands for function") + tok.name);
                        }

                        // Only 16 parameters for now
                        // This function would benefit from variable size arrays
                        Number params[16];

                        for (std::size_t i = func.arity ; i > 0u ; --i)
                        {
                            params[i-1u] = operands.top();
                            operands.pop();
                        }
                        operands.push(func(params));
                        break;
                    }

                    case token_t::infix:
                    {
                        if (operands.size() < 2)
                        {
                            throw error(error_code::not_enough_operands, to_string(tok.infix));
                        }
                        Number rhs = operands.top();
                        operands.pop();
                        Number lhs = operands.top();
                        operands.pop();
                        operands.push(operation(tok.infix, lhs, rhs));
                        break;
                    }

                    case token_t::prefix:
                    {
                        if (operands.empty())
                        {
                            throw error(error_code::not_enough_operands, to_string(tok.prefix));
                        }
                        Number arg = operands.top();
                        operands.pop();
                        operands.push(operation(tok.prefix, arg));
                        break;
                    }

                    case token_t::postfix:
                    {
                        if (operands.empty())
                        {
                            throw error(error_code::not_enough_operands, to_string(tok.postfix));
                        }
                        Number arg = operands.top();
                        operands.pop();
                        operands.push(operation(tok.postfix, arg));
                        break;
                    }

                    default:
                        throw error("unexpected token in postfix evaluation: " + to_string(tok));
                }
            }
            return operands.top();
        }

        std::unordered_map<std::string, callback<Number>> callbacks;
};

As you can see, many things are going on here. Namely, we can see:

  • A callback mechanism.
  • A token mechanism.
  • A tokenization function (a lexer).
  • A shunting-yard algorithm to convert the tokens to a postfix form.
  • A function to evaluate the postfix expression (eval_postfix in the evaluator).
  • Data about the operators.
  • An error reporting mechanism.

The evaluation mechanism itself is quite simple: tokenize the expression, use the shunting-yard algorithm to convert it to reverse Polish notation (producing the postfix expression) then evaluate this postfix expression to finally produce the desired result.

Now, we will see one by one every each of these components. I hope that the code is fragmented enough to be easily readable. Also, note that everything is supposed to live in the namespace polder, that I stripped for the review since it would only be cognitive noise for reviewers.

Actually, the code is too huge to fit in a single question, so I will split it into two parts. This one will be about the logic and the algorithms while the second one will mostly be about the architecture.

The callback mechanism

/**
 * @brief Evaluation callback function.
 *
 * This class abstracts away a function that takes a given
 * number of parameters of a same type and returns a result
 * of this type.
 *
 * It is especially designed so that the number of parameters
 * of the function is kept, but is not part of the type. A
 * callback can be called with a pointer to an array of the
 * templated type and will manage to call the original function
 * with that array.
 */
template<typename Number>
class callback
{
    public:

        /**
         * Convert the given function to a callback.
         */
        template<typename Func>
        callback(Func&& function):
            callback(
                std::forward<Func>(function),
                std::make_index_sequence<
                    function_traits<Func>::arity
                >{}
            )
        {}

        /**
         * Call the original function with an array of Number
         * where the elements of the array correspond to the
         * parameters to feed to the original function.
         */
        auto operator()(Number* args) const
            -> Number
        {
            return _func(args);
        }

        const std::size_t arity; /**< Number of parameters that the function takes */

    private:

        template<typename Func, std::size_t... Ind>
        callback(Func&& function, std::index_sequence<Ind...>):
            arity(sizeof...(Ind)),
            _func([function](Number* args)
            {
                return function(args[Ind]...);
            })
        {}

        std::function<Number(Number*)> _func;
};

That one is actually rather tricky so here is a little explanation: when the user registers a function, actually, the function itself is not registered, but wrapped into a lambda that takes a Number* parameter (an array of Number) and uses the [indices trick][3] in order to call the original function with the correct number of parameters.

Since the evaluator only works with instances of a given type, the callbacks can only take a number of parameters of this type. Also, it's currently limited to 16 parameters (the limitation appears somewhere else, not in the callback code), but who needs 16 parameters anyway?

The lexer

This is a hand-rolled lexer. I could have used a lexer tool but I decided to roll my own. This is how I roll. I takes a string and converts it to a vector of tokens.

template<typename Number>
auto tokenize(const std::string& expr)
    -> std::vector<token<Number>>
{
    std::vector<token<Number>> res;

    // Number of parenthesis
    int nmb_parenthesis = 0;

    for (auto it = expr.cbegin() ; it != expr.cend() ; ++it)
    {
        // Skip all kinds of spaces
        while (std::isspace(*it))
        {
            ++it;
        }
        if (*it == '\0')
        {
            break;
        }

        if (std::isdigit(*it))
        {
            // Found a number
            auto tmp = it;
            bool has_dot = false;
            while (std::isdigit(*it) || *it == '.')
            {
                if (*it == '.')
                {
                    if (has_dot)
                    {
                        // Two dots in the same number: error
                        throw error(error_code::unexpected_character, '.');
                    }
                    else
                    {
                        // We just confirmed we found a real number
                        has_dot = true;
                    }
                }
                ++it;
            }
            auto tmp_str = std::string(tmp, it);
            res.emplace_back(std::stod(tmp_str));
            --it; // Iteration is pushed one step too far
            continue;
        }

        if (std::isalpha(*it) || *it == '_')
        {
            // Found a function name
            auto tmp = it;
            while (std::isalnum(*it) || *it == '_')
            {
                ++it;
            }
            res.emplace_back(std::string(tmp, it));
            --it; // Iteration is pushed one step too far
            continue;
        }

        switch (*it)
        {
            case ',':
                if (nmb_parenthesis == 0)
                {
                    throw error("a comma can not appear outside of a function's parameter list");
                }
                res.emplace_back(token_t::comma);
                break;

            case ')':
                if (nmb_parenthesis == 0)
                {
                    throw error("trying to close a non-opened parenthesis");
                }
                --nmb_parenthesis;
                res.emplace_back(token_t::right_brace);
                break;

            case '(':
                ++nmb_parenthesis;
                res.emplace_back(token_t::left_brace);
                break;

            case '+':
                res.emplace_back(infix_t::ADD);
                break;
            case '%':
                res.emplace_back(infix_t::MOD);
                break;
            case '~':
                res.emplace_back(prefix_t::BNOT);
                break;
            case '=':
                res.emplace_back(infix_t::EQ);
                break;

            case '*': // * or **
                if (it[1] == '*')
                {
                    res.emplace_back(infix_t::POW);
                    ++it;
                }
                else
                {
                    res.emplace_back(infix_t::MUL);
                }
                break;

            case '&': // & or &&
                if (it[1] == '&')
                {
                    res.emplace_back(infix_t::AND);
                    ++it;
                }
                else
                {
                    res.emplace_back(infix_t::BAND);
                }
                break;

            case '|': // | or ||
                if (it[1] == '*')
                {
                    res.emplace_back(infix_t::OR);
                    ++it;
                }
                else
                {
                    res.emplace_back(infix_t::BOR);
                }
                break;

            case '^': // ^ or ^^
                if (it[1] == '^')
                {
                    res.emplace_back(infix_t::XOR);
                    ++it;
                }
                else
                {
                    res.emplace_back(infix_t::BXOR);
                }
                break;

            case '/': // / or //
                if (it[1] == '/')
                {
                    res.emplace_back(infix_t::IDIV);
                    ++it;
                }
                else
                {
                    res.emplace_back(infix_t::DIV);
                }
                break;

            case '-': // - (unary or binary)
                if (res.empty())
                {
                    res.emplace_back(prefix_t::USUB);
                    break;
                }
                else
                {
                    const token<Number>& tok = res.back();
                    if (tok.is_operand()
                        || tok.is_postfix()
                        || tok.is_right_brace())
                    {
                        res.emplace_back(infix_t::SUB);
                    }
                    else
                    {
                        res.emplace_back(prefix_t::USUB);
                    }
                    break;
                }

            case '<': // <, <=, <=>, << and <>
                if (it[1] == '<')
                {
                    res.emplace_back(infix_t::LSHIFT);
                    ++it;
                    break;
                }
                else if (it[1] == '>')
                {
                    res.emplace_back(infix_t::NE);
                    ++it;
                    break;
                }
                else if (it[1] == '=')
                {
                    if (it[2] == '>')
                    {
                        res.emplace_back(infix_t::SPACE);
                        it += 2;
                        break;
                    }
                    res.emplace_back(infix_t::LE);
                    ++it;
                    break;
                }
                res.emplace_back(infix_t::LT);
                break;

            case '>': // >, >= and >>
                if (it[1] == '>')
                {
                    res.emplace_back(infix_t::RSHIFT);
                    ++it;
                    break;
                }
                else if (it[1] == '=')
                {
                    res.emplace_back(infix_t::GE);
                    ++it;
                    break;
                }
                res.emplace_back(infix_t::GT);
                break;

            case '!': // ! (prefix or postfix) and !=
                if (it[1] == '=' && it[1] != '=')
                {
                    res.emplace_back(infix_t::NE);
                    break;
                }
                else
                {
                    const token<Number>& tok = res.back();
                    if (tok.is_operand()
                        || tok.is_postfix()
                        || tok.is_right_brace())
                    {
                        res.emplace_back(postfix_t::FAC);
                        break;
                    }
                    res.emplace_back(prefix_t::NOT);
                    break;
                }

            default:
                throw error(error_code::unknown_operator, *it);
        }
    }

    if (nmb_parenthesis)
    {
        throw error("mismatched parenthesis in the expression");
    }

    return res;
}

The shunting-yard algorithm

This algorithm is derived from the one described in the Wikipedia page linked earlier in the description. I only tweaked it a little bit so that it can also handle the prefix and postfix operators. Therefore there is probably still some room for improvement.

template<typename Number>
auto to_postfix(const std::vector<token<Number>>& tokens)
    -> std::stack<token<Number>>
{
    // This function implements a Shunting-Yard algorithm
    // to handle the priority of infix operators

    std::stack<token<Number>> output;
    std::stack<token<Number>> operations;

    for (const token<Number>& tok: tokens)
    {
        switch (tok.type)
        {
            case token_t::operand:
            {
                output.push(tok);
                while (not operations.empty() && operations.top().is_prefix())
                {
                    output.push(operations.top());
                    operations.pop();
                }
                break;
            }

            case token_t::postfix:
            {
                output.push(tok);
                break;
            }

            case token_t::infix:
            {
                while (not operations.empty()
                       && operations.top().is_infix()
                       && (priority(tok.infix) <= priority(operations.top().infix)))
                {
                    output.push(operations.top());
                    operations.pop();
                }
                operations.push(tok);
                break;
            }

            case token_t::prefix:
            case token_t::name:
            case token_t::left_brace:
            {
                operations.push(tok);
                break;
            }

            case token_t::right_brace:
            {
                while (not operations.empty() &&
                       not operations.top().is_left_brace())
                {
                    output.push(operations.top());
                    operations.pop();
                }
                operations.pop();
                while (not operations.empty()
                       && (operations.top().is_prefix() || operations.top().is_name()))
                {
                    output.push(operations.top());
                    operations.pop();
                }
                break;
            }

            case token_t::comma:
            {
                while (not operations.empty() &&
                       not operations.top().is_left_brace())
                {
                    output.push(operations.top());
                    operations.pop();
                }
                break;
            }
        }
    }

    while (not output.empty())
    {
        operations.push(output.top());
        output.pop();
    }
    return operations;
}

So, this is where the interesting part of the question ends. But there is a twin question that presents the "architecture" of the evaluator, namely the "small" classes that are used by the evaluator, also known as all these things that are not really interesting but essential to make the whole thing work. You might want to go back and forth between the two of them to understand everything. Don't hesitate to ask questions if there is something you didn't understand.

Source code

You might want to have a look at the real source code which I slightly modified for this review. Here are the links:

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

Suspected Bugs:

A typo I think

     case '|': // | or ||
            if (it[1] == '*')

Stylistic differences:

A couple of things I would do differently.
But I believe you and I differ on these minor stylistic things:

User defined Types

I prefer to use an initial caps when defining types. It helps distinguish types from objects.

New Style auto return

I still prefer the old style of function declaration over the new style.

// old style
std::vector<token<Number>> tokenize(const std::string& expr)

// new style
auto tokenize(const std::string& expr) -> std::vector<token<Number>>

I use the new style only when the return type depends on the inputs.

Lexer

I would have used a lexer tool. That's how I roll.

Hard To spot break

       case '-': // - (unary or binary)
            if (res.empty())
            {
                // STUFF
                break
            }
            else
            {
                // STUFF
                break;
            }

Personally I would move the breaks outside the if statement. So it is clear that the case statement does have a break.

        case '-': // - (unary or binary)
            if (res.empty())
            {
                // STUFF
            }
            else
            {
                // STUFF
            }
            break;

Same thing in:

case '!': // ! (prefix or postfix) and !=

Changes that may help:

Limit of 16 parameters

                   Number params[16];
                    //  STUFF
                    operands.push(func(params));
                    break;

Why not use a std::vector?
You can still pass it as an array pointer by taking the address of the first argument.

                    std::vector<Number> x;
                    //  STUFF
                    operands.push(func(&params[0]));
                    break;

New Stuff:

Not seen this before

       callbacks.emplace(
            std::piecewise_construct,     // Will have to go read about this.
            std::forward_as_tuple(name),
            std::forward_as_tuple(function)
        );

Would using move semantics help for future

output.push(operations.top());

In the future it may be more than just numbers that you use in the expression. You want to prepare for that by using move semantics when transfering values in a couple of places.

output.push(std::move(operations.top()));
\$\endgroup\$
  • \$\begingroup\$ Well, from what we've seen in the numerous questions and answers, we do have some different tastes when it comes to style :) At first I capitalized all my types, but I have written many types where I used the constructor as a "function" or types that were designed to look like types from the standard library. So in the end I choosed the snake_case_everywhere since I mostly write library stuff :) \$\endgroup\$ – Morwenn May 23 '15 at 22:50
  • \$\begingroup\$ I indeed considered using an std::vector instead of a static array for the parameters, but I decided that nobody would need more than 16 parameters anyway and that using a full std::vector for that wasn't a bit overkill. Actually, that's one of these few places where I would have used a VLA if available. \$\endgroup\$ – Morwenn May 23 '15 at 22:52
  • \$\begingroup\$ There was indeed a bug due to a typo though. Also using move semantics where possible is a really good idea, I will probably incorporate that and the break stuff to the code. Thanks again :) \$\endgroup\$ – Morwenn May 23 '15 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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