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
callbackmechanism. - 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_postfixin 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:
- Global include file
- Base directory for the
.hand.inlfiles (the latter are indetails). - Base directory for the
.cppfiles. - Dedicated testsuite file.
