11
\$\begingroup\$

This question goes hand in hand with another question about a mathematical expressions evaluator in C++. The other question is meant to be read first, this one is but a complement to expose the internals of the evaluator and the overall architecture to explain how the details work.

The tokens mechanism

A token is a hand-rolled tagged union (I would have used Boost.Variant but the code only relies on the standard library) which can contain any kind of token that can appear in a mathematical expression:

/**
 * Token types that can be used by the evaluator.
 */
enum struct token_t:
    std::uint_fast8_t
{
    operand,
    name,
    infix,
    prefix,
    postfix,
    left_brace,
    right_brace,
    comma
};

/**
 * Token used by the evaluator. It can either represent
 * a parenthesis, an operator or a number. Number types
 * are restricted to built-in types.
 */
template<typename Number>
struct token
{
    ////////////////////////////////////////////////////////////
    // Construction and destruction

    token(const token& other):
        type(other.type)
    {
        switch (type)
        {
            case token_t::operand:
                data = other.data;
                break;
            case token_t::name:
                new (&name) std::string;
                name = other.name;
                break;
            case token_t::infix:
                infix = other.infix;
                break;
            case token_t::prefix:
                prefix = other.prefix;
                break;
            case token_t::postfix:
                postfix = other.postfix;
                break;

            default:
                // Do fucking nothing and shut the compiler warning
                break;
        }
    }

    explicit token(token_t type):
        type(type)
    {
        if (type == token_t::name)
        {
            new (&name) std::string;
        }
    }

    explicit token(Number num):
        type(token_t::operand),
        data(num)
    {}

    explicit token(std::string name):
        type(token_t::name)
    {
        new (&this->name) std::string;
        this->name = std::move(name);
    }

    explicit token(infix_t oper):
        type(token_t::infix),
        infix(oper)
    {}

    explicit token(prefix_t oper):
        type(token_t::prefix),
        prefix(oper)
    {}

    explicit token(postfix_t oper):
        type(token_t::postfix),
        postfix(oper)
    {}

    ~token()
    {
        if (type == token_t::name)
        {
            name.~basic_string();
        }
    }

    ////////////////////////////////////////////////////////////
    // Helper functions

    auto is_operand() const
        -> bool
    {
        return type == token_t::operand;
    }

    auto is_name() const
        -> bool
    {
        return type == token_t::name;
    }

    auto is_infix() const
        -> bool
    {
        return type == token_t::infix;
    }

    auto is_prefix() const
        -> bool
    {
        return type == token_t::prefix;
    }

    auto is_postfix() const
        -> bool
    {
        return type == token_t::postfix;
    }

    auto is_left_brace() const
        -> bool
    {
        return type == token_t::left_brace;
    }

    auto is_right_brace() const
        -> bool
    {
        return type == token_t::right_brace;
    }

    auto is_comma() const
        -> bool
    {
        return type == token_t::comma;
    }

    ////////////////////////////////////////////////////////////
    // Member data

    const token_t type;

    union
    {
        Number data;
        std::string name;
        infix_t infix;
        prefix_t prefix;
        postfix_t postfix;
    };
};

////////////////////////////////////////////////////////////
// Display functions

template<typename Number>
auto to_string(const token<Number>& tok)
    -> std::string
{
    switch (tok.type)
    {
        case token_t::operand:
            return std::to_string(tok.data);
        case token_t::name:
            return tok.name;
        case token_t::infix:
            return to_string(tok.infix);
        case token_t::prefix:
            return to_string(tok.prefix);
        case token_t::postfix:
            return to_string(tok.postfix);
        case token_t::left_brace:
            return "(";
        case token_t::right_brace:
            return ")";
        case token_t::comma:
            return ",";
    }

    // Should never be reached
    return "";
}

template<typename Number>
auto operator<<(std::ostream& stream, const token<Number>& tok)
    -> std::ostream&
{
    switch (tok.type)
    {
        case token_t::operand:
            stream << tok.data;
            break;
        case token_t::name:
            stream << tok.name;
            break;
        case token_t::infix:
            stream << to_string(tok.infix);
            break;
        case token_t::prefix:
            stream << to_string(tok.prefix);
            break;
        case token_t::postfix:
            stream << to_string(tok.postfix);
            break;
        case token_t::left_brace:
            stream << '(';
            break;
        case token_t::right_brace:
            stream << ')';
            break;
        case token_t::comma:
            stream << ',';
            break;
    }
    return stream;
}

The code for token is mostly redundant so there is probably room for improvement. Also, many parts of the code treat infix, prefix and postfix almost the same way. I bet that I could do some clever things to reduce the code while keeping a strong type safety.

The operators

As you have seen, some functions, namely priority and operation, are invoked of operator tokens. These function respectively find the priority of an operator and apply the given operator to the given values. Here they are, with some additional data about the operators.

operator.cpp

namespace
{
    constexpr unsigned int infix_priority[] = {
        7,   // =
        7,   // !=, <>
        8,   // >=
        8,   // <=
        3,   // &&
        1,   // ||
        2,   // ^^
        12,  // **
        7,   // <=>
        9,   // <<
        9,   // >>
        10,  // +
        10,  // -
        11,  // *
        11,  // /
        11,  // %
        6,   // &
        4,   // |
        8,   // >
        8,   // <
        5,   // ^
        11,  // //
    };

    constexpr const char* infix_str[] = {
        "=",
        "!=",
        ">=",
        "<=",
        "&&",
        "||",
        "^^",
        "**",
        "<=>",
        "<<",
        ">>",
        "+",
        "-",
        "*",
        "/",
        "%",
        "&",
        "|",
        ">",
        "<",
        "^",
        "//"
    };

    constexpr const char* prefix_str[] = {
        "-",
        "!",
        "~"
    };

    constexpr const char* postfix_str[] = {
        "!"
    };
}

////////////////////////////////////////////////////////////
// Priority of infix operators

auto priority(infix_t oper)
    -> unsigned int
{
    return infix_priority[
        std::underlying_type_t<infix_t>(oper)
    ];
}

////////////////////////////////////////////////////////////
// String conversion functions

auto to_string(infix_t oper)
    -> std::string
{
    return infix_str[
        std::underlying_type_t<infix_t>(oper)
    ];
}

auto to_string(prefix_t oper)
    -> std::string
{
    return prefix_str[
        std::underlying_type_t<prefix_t>(oper)
    ];
}

auto to_string(postfix_t oper)
    -> std::string
{
    return postfix_str[
        std::underlying_type_t<postfix_t>(oper)
    ];
}

operation.inl

template<typename Number>
auto operation(infix_t oper, Number lhs, Number rhs)
    -> Number
{
    static const std::unordered_map<infix_t, Number(*)(Number, Number), enum_hash<infix_t>> operations = {
        { infix_t::ADD,    [](Number a, Number b) -> Number { return a + b; } },
        { infix_t::SUB,    [](Number a, Number b) -> Number { return a - b; } },
        { infix_t::MUL,    [](Number a, Number b) -> Number { return a * b; } },
        { infix_t::LT,     [](Number a, Number b) -> Number { return a < b; } },
        { infix_t::GT,     [](Number a, Number b) -> Number { return a > b; } },
        { infix_t::DIV,    [](Number a, Number b) -> Number { return a / b; } },
        { infix_t::IDIV,   [](Number a, Number b) -> Number { return (long long) a / (long long) b; } },
        { infix_t::MOD,    [](Number a, Number b) -> Number { return (long long) a % (long long) b; } },
        { infix_t::BAND,   [](Number a, Number b) -> Number { return (long long) a & (long long) b; } },
        { infix_t::BXOR,   [](Number a, Number b) -> Number { return (long long) a ^ (long long) b; } },
        { infix_t::BOR,    [](Number a, Number b) -> Number { return (long long) a | (long long) b; } },
        { infix_t::EQ,     [](Number a, Number b) -> Number { return a == b; } },
        { infix_t::NE,     [](Number a, Number b) -> Number { return a != b; } },
        { infix_t::GE,     [](Number a, Number b) -> Number { return a >= b; } },
        { infix_t::LE,     [](Number a, Number b) -> Number { return a <= b; } },
        { infix_t::AND,    [](Number a, Number b) -> Number { return a && b; } },
        { infix_t::XOR,    [](Number a, Number b) -> Number { return (a && !b) || (b && !a); } },
        { infix_t::OR,     [](Number a, Number b) -> Number { return a || b; } },
        { infix_t::POW,    [](Number a, Number b) -> Number { return std::pow(a, b); } },
        { infix_t::SPACE,  [](Number a, Number b) -> Number { return (a < b) ? -1 : (a != b); } },
        { infix_t::LSHIFT, [](Number a, Number b) -> Number { return (long long) a << (long long) b; } },
        { infix_t::RSHIFT, [](Number a, Number b) -> Number { return (long long) a >> (long long) b; } }
    };

    auto it = operations.find(oper);
    if (it == operations.end())
    {
        throw error(error_code::unknown_operator, oper);
    }
    return it->second(lhs, rhs);
}

template<typename Number>
auto operation(prefix_t oper, Number arg)
    -> Number
{
    static const std::unordered_map<prefix_t, Number(*)(Number), enum_hash<prefix_t>> operations = {
        { prefix_t::USUB,  [](Number a) -> Number { return -a; } },
        { prefix_t::NOT,   [](Number a) -> Number { return !a; } },
        { prefix_t::BNOT,  [](Number a) -> Number { return ~ (long long) a; } }
    };

    auto it = operations.find(oper);
    if (it == operations.end())
    {
        throw error(error_code::unknown_operator, oper);
    }
    return it->second(arg);
}

template<typename Number>
auto operation(postfix_t oper, Number arg)
    -> Number
{
    static const std::unordered_map<postfix_t, Number(*)(Number), enum_hash<postfix_t>> operations = {
        { postfix_t::FAC,    [](Number a) -> Number { return math::factorial((unsigned long long) a); } }
    };

    auto it = operations.find(oper);
    if (it == operations.end())
    {
        throw error(error_code::unknown_operator, oper);
    }
    return it->second(arg);
}

The error reporting mechanism

Finally, here is the source code of the error reporting mechanism. It is exception-based and don't worry about the generic name error, everything is wrapped in the namespace polder::evaluation, which I did not include for the review to reduce the cognitive noise. So, the thing is exception-based and split into two files, a header and a .cpp file since I didn't need templates for the errors.

error.h

/**
 * Error codes fed to the exceptions to specify
 * which kind of error has been thrown.
 */
enum struct error_code:
    std::uint_fast8_t
{
    unknown_operator,
    unexpected_character,
    not_enough_operands
};

/**
 * Exceptions raised when a syntax error is
 * found in the expression to evaluate.
 */
class POLDER_API error:
    public std::exception
{
    public:

        explicit error();
        explicit error(const std::string& arg);
        error(error_code err, char c);
        error(error_code err, infix_t oper);
        error(error_code err, prefix_t oper);
        error(error_code err, postfix_t oper);
        error(error_code err, const std::string& arg);

        virtual ~error() override;

        virtual auto what() const noexcept
            -> const char*
            override;

    private:

        std::string msg; /**< Error message */
};

In case you wonder what it is, POLDER_API is a macro to ensure that the library can be compiled as a static library or as a dynamic one. It is common practice so I won't comment further about it.

error.cpp

using namespace std::string_literals;

error::error():
    msg("polder::evaluation::error: undocumented error")
{}

error::error(const std::string& arg):
    msg("polder::evaluation::error: "s += arg)
{}

error::error(error_code err, char c)
{
    std::ostringstream oss;
    oss << "polder::evaluation::error: ";

    switch (err)
    {
        case error_code::unknown_operator:
            oss << "unknown operator '" << c << "' in the expression";
            break;
        case error_code::unexpected_character:
            oss << "unexpected character '" << c <<"' in the expression";
            break;
        default:
            oss << "unknown error in the expression";
            break;
    }

    msg = oss.str();
}

error::error(error_code err, infix_t oper)
{
    std::ostringstream oss;
    oss << "polder::evaluation::error: ";

    switch (err)
    {
        case error_code::unknown_operator:
            oss << "unknown operator '" << to_string(oper) << "' in the expression";
            break;
        default:
            oss << "unknown error in the expression";
            break;
    }

    msg = oss.str();
}

error::error(error_code err, prefix_t oper)
{
    std::ostringstream oss;
    oss << "polder::evaluation::error: ";

    switch (err)
    {
        case error_code::unknown_operator:
            oss << "unknown operator '" << to_string(oper) << "' in the expression";
            break;
        default:
            oss << "unknown error in the expression";
            break;
    }

    msg = oss.str();
}

error::error(error_code err, postfix_t oper)
{
    std::ostringstream oss;
    oss << "polder::evaluation::error: ";

    switch (err)
    {
        case error_code::unknown_operator:
            oss << "unknown operator '" << to_string(oper) << "' in the expression";
            break;
        default:
            oss << "unknown error in the expression";
            break;
    }

    msg = oss.str();
}

error::error(error_code err, const std::string& arg)
{
    std::ostringstream oss;
    oss << "polder::evaluation::error: ";

    switch (err)
    {
        case error_code::unknown_operator:
            oss << "unknown operator '" << arg << "' in the expression";
            break;
        case error_code::not_enough_operands:
            oss << "not enough operands for operator '" << arg << "'.";
            break;
        default:
            oss << "unknown error in the expression";
            break;
    }

    msg = oss.str();
}

error::~error() noexcept
    = default;

auto error::what() const noexcept
    -> const char*
{
    return msg.c_str();
}

Miscellaneous utilities

While reading the two questions (did you?), you may have noticed some utility functions and classes that are not part of the standard library or part of the evaluation tool. They come from the POLDER library whose the evaluation module is part of. Here are the ones I noticed. Comment if one of them wasn't documented:

  • math::factorial: that may be obvious, but this is a factorial function. Nothing suprising here.

  • enum_hash: I am using C++14, so technically enum types should be automagically hashed as their underlying type. Unfortunately, this is not implemented everywhere, so I provided a simple generic hash object for enum types. It should go away once enum types are correctly hashed.

  • function_traits: this is an enhanced version of boost::function_traits which can provide the type of the \$n\$th parameter of a function thanks to a template integer. We only use it to get the arity of the callbacks.

\$\endgroup\$
2
\$\begingroup\$
$ clang++ -std=c++1y -Iinclude -o src/POLDER/evaluation/error.o -c src/POLDER/evaluation/error.cpp
src/POLDER/evaluation/error.cpp:131:12: warning: function previously declared
      with an implicit exception specification redeclared with an explicit
      exception specification [-Wimplicit-exception-spec-mismatch]
    error::~error() noexcept
           ^
include/POLDER/evaluation/error.h:63:21: note: previous declaration is here
            virtual ~error() override;
                    ^
1 warning generated.
\$\endgroup\$
  • \$\begingroup\$ True. I don't even know why I added noexcept to the destructor since it's implicit in the first place .___. Thanks :) \$\endgroup\$ – Morwenn May 23 '15 at 22:44

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.