Simple calculator in C++

calc.cpp

#include <array>
#include <istream>
#include <limits>
#include <memory>
#include <optional>
#include <sstream>
#include <string>
#include <variant>

struct SyntaxError : public std::runtime_error {
    explicit SyntaxError(const std::string& what) : std::runtime_error(what) {
    }
};

struct ConstantToken {
    int64_t number = 0;
};

inline bool operator==(ConstantToken lhs, ConstantToken rhs) {
    return lhs.number == rhs.number;
}

enum class BracketToken {
    OPEN,
    CLOSE,
};

struct SymbolToken {
    char symbol = '\0';
};

inline bool operator==(const SymbolToken& lhs, const SymbolToken& rhs) {
    return lhs.symbol == rhs.symbol;
}

using Token = std::variant<ConstantToken, BracketToken, SymbolToken>;

namespace impl {

enum ETokenizationState {
    kStart,

    kNumber,
    kOperator,

    kBeforeFirstFinishState,
    kNumberFinish,
    kBracketFinish,
    kOperatorFinish,
    kInvalidFinish,
    kAfterLastFinishState,

    kEndOfFile,

    kNumStates,
};

namespace char_class {

template <unsigned char begin, unsigned char end>
inline constexpr auto GenCharRange() {
    std::array<unsigned char, end - begin + 1> res = {0};
    for (size_t i = 0; i < res.size(); ++i) {
        res[i] = begin + i;
    }
    return res;
}

static inline constexpr auto kDigits = GenCharRange<'0', '9'>();
static inline constexpr std::array<unsigned char, 4> kOperators = {'-', '+', '*', '/'};
static inline constexpr std::array<unsigned char, 2> kBrackets = {'(', ')'};

}  // namespace char_class

struct NextState {
    ETokenizationState state = ETokenizationState::kStart;
    bool should_consume_char = false;
};

class StateMachine {
public:
    NextState Feed(ETokenizationState state, int c) const {
        if (c == std::char_traits<char>::eof()) {
            return Feed(state, kEOF);
        }
        return table_[state][static_cast<size_t>(c)];
    }

    static const StateMachine& Instance() {
        static StateMachine machine;
        return machine;
    }

private:
    StateMachine() {
        FillDefaults();
        RegisterSpace();
        RegisterEof();
        RegisterConstants();
        RegisterBrackets();
        RegisterSymbols();
    }

    void FillDefaults() {
        for (auto& row : table_) {
            row.fill(NextState{kInvalidFinish, false});
        }

        table_[kNumber].fill(NextState{kNumberFinish, false});
    }

    void RegisterSpace() {
        for (unsigned char c = '\x01'; c; ++c) {
            if (::isspace(c)) {
                table_[kStart][c] = NextState{kStart, true};
            }
        }
    }

    void RegisterEof() {
        table_[kStart][kEOF] = NextState{kEndOfFile, false};
    }

    void RegisterConstants() {
        for (unsigned char c : char_class::kDigits) {
            table_[kStart][c] = NextState{kNumber, true};
            table_[kNumber][c] = NextState{kNumber, true};
        }
    }

    void RegisterBrackets() {
        for (unsigned char c : char_class::kBrackets) {
            table_[kStart][c] = NextState{kBracketFinish, true};
        }
    }

    void RegisterSymbols() {
        for (unsigned char c : char_class::kOperators) {
            table_[kStart][c] = NextState{kOperatorFinish, true};
        }
    }

private:
    static inline constexpr size_t kEOF = size_t{std::numeric_limits<unsigned char>::max()} + 1;
    static inline constexpr size_t kSize = kEOF + 1;
    std::array<std::array<NextState, kSize>, kNumStates> table_;
};

inline bool IsFinish(ETokenizationState state) {
    return kBeforeFirstFinishState < state && state < kAfterLastFinishState;
}

inline ConstantToken ParseNumber(std::string_view s) {
    std::istringstream ss{std::string{s}};

    ConstantToken token;
    ss >> token.number;

    return token;
}

inline BracketToken ParseBracket(std::string_view s) {
    switch (s[0]) {
        case '(':
            return BracketToken::OPEN;
        case ')':
            return BracketToken::CLOSE;
        default:
            __builtin_unreachable();
    }
}

inline SymbolToken ParseSymbol(std::string_view s) {
    return SymbolToken{s[0]};
}

inline Token ClassifyToken(ETokenizationState state, std::string_view result) {
    switch (state) {
        case kNumberFinish:
            return ParseNumber(result);
        case kBracketFinish:
            return ParseBracket(result);
        case kOperatorFinish:
            return ParseSymbol(result);
        case kInvalidFinish:
            throw SyntaxError{"Invalid token found"};
        default:
            __builtin_unreachable();
    };
}

}  // namespace impl

class Tokenizer {
public:
    Tokenizer(std::istream* is) : stream_{is} {
        Next();
    }

    bool IsEnd() const {
        return !token_ && stream_->eof();
    }

    Token GetToken() const {
        if (!token_.has_value()) {
            throw SyntaxError{"Unexpected EOF"};
        }
        return *token_;
    }

    void Next() {
        DoReadToken();
    }

private:
    void SkipSpaces() {
        while (std::isspace(stream_->peek())) {
            stream_->get();
        }
    }

    void DoReadToken() {
        std::string token;

        impl::ETokenizationState state = impl::kStart;
        for (int c = stream_->peek(); true; c = stream_->peek()) {
            auto result = impl::StateMachine::Instance().Feed(state, c);

            if (result.should_consume_char) {
                if (result.state != impl::kStart) {
                    token.push_back(c);
                }
                stream_->get();
            }

            state = result.state;

            if (state == impl::kEndOfFile) {
                break;
            }

            if (IsFinish(state)) {
                token_ = ClassifyToken(state, token);
                return;
            }
        }

        token_ = std::nullopt;
    }

private:
    std::istream* stream_ = nullptr;
    std::optional<Token> token_;
};

/*
<expression> ::= <additive-expression>
<additive-expression> ::= <multiplicative-expression>
    | <multiplicative-expression> + <additive-expression>
    | <multiplicative-expression> - <additive-expression>
<multiplicative-expression> ::= <unary-expression>
    | <unary-expression> * <multiplicative-expression>
    | <unary-expression> / <multiplicative-expression>
<unary-expression> ::= <primary_expression>
    | + <unary-expression>
    | - <unary-expression>
<primary_expression> ::= <integer_literal>
    | (<expression>)
<integer-literal> ::= <digit>
    | <integer_literal><digit>
<digit> ::= [0-9]
*/

class Expression {
public:
    virtual ~Expression() = default;

    virtual int64_t Evaluate() = 0;
};

class BinaryFunctorExpressionBase : public Expression {
public:
    BinaryFunctorExpressionBase(std::unique_ptr<Expression> left = {},
                                std::unique_ptr<Expression> right = {})
        : left_{std::move(left)}, right_{std::move(right)} {
    }

protected:
    std::unique_ptr<Expression> left_;
    std::unique_ptr<Expression> right_;
};

template <typename F, int64_t Identity>
class FunctorExpression final : public BinaryFunctorExpressionBase {
public:
    FunctorExpression(std::unique_ptr<Expression> left = {}, std::unique_ptr<Expression> right = {})
        : BinaryFunctorExpressionBase{std::move(left), std::move(right)} {
    }

    int64_t Evaluate() override {
        int64_t result = Identity;
        if (left_) {
            result = left_->Evaluate();
        }
        if (right_) {
            result = F{}(result, right_->Evaluate());
        }
        return result;
    }
};

class ConstantExpression final : public Expression {
public:
    ConstantExpression(int64_t value) : value_{value} {
    }

    int64_t Evaluate() override {
        return value_;
    }

private:
    int64_t value_;
};

inline std::unique_ptr<BinaryFunctorExpressionBase> DispatchOperator(char op, std::unique_ptr<Expression> lhs, std::unique_ptr<Expression> rhs) {
    switch (op) {
        case '+':
            return std::make_unique<FunctorExpression<std::plus<>, 0>>(std::move(lhs), std::move(rhs));
        case '-':
            return std::make_unique<FunctorExpression<std::minus<>, 0>>(std::move(lhs), std::move(rhs));
        case '*':
            return std::make_unique<FunctorExpression<std::multiplies<>, 1>>(std::move(lhs), std::move(rhs));
        case '/':
            return std::make_unique<FunctorExpression<std::divides<>, 1>>(std::move(lhs), std::move(rhs));
        default:
            throw SyntaxError{"Unknown operator"};
    }
}

inline std::unique_ptr<Expression> ParseExpression(Tokenizer* tok);
inline std::unique_ptr<Expression> ParseAdditiveExpression(Tokenizer* tok);
inline std::unique_ptr<Expression> ParseMultiplicativeExpression(Tokenizer* tok);
inline std::unique_ptr<Expression> ParseUnaryExpression(Tokenizer* tok);
inline std::unique_ptr<Expression> ParsePrimaryExpression(Tokenizer* tok);
inline std::unique_ptr<Expression> ParseIntegerLiteral(Tokenizer* tok);

inline std::unique_ptr<Expression> ParsePrimaryExpression(Tokenizer* tokenizer) {
    auto token = tokenizer->GetToken();
    if (auto ptr = std::get_if<BracketToken>(&token)) {
        switch (*ptr) {
            case BracketToken::OPEN: {
                tokenizer->Next();
                auto expr = ParseExpression(tokenizer);
                auto token = tokenizer->GetToken();
                if (auto ptr = std::get_if<BracketToken>(&token); !ptr || *ptr != BracketToken::CLOSE) {
                    throw SyntaxError{"Close bracket expected"};
                }
                tokenizer->Next();
                return expr;
            }
            default:
                break;
        }
    }

    try {
        tokenizer->Next();
        return std::make_unique<ConstantExpression>(std::get<ConstantToken>(token).number);
    } catch (...) {
        throw SyntaxError{"Expected number"};
    }
}

inline std::unique_ptr<Expression> ParseUnaryExpression(Tokenizer* tokenizer) {
    auto token = tokenizer->GetToken();
    if (auto ptr = std::get_if<SymbolToken>(&token)) {
        switch (ptr->symbol) {
            case '+':
            case '-':
                tokenizer->Next();
                return DispatchOperator(ptr->symbol, nullptr, ParseUnaryExpression(tokenizer));
            default:
                break;
        }
    }

    std::unique_ptr<Expression> left = ParsePrimaryExpression(tokenizer);

    return left;
}

template <char... Ops, typename ArgParser>
inline std::unique_ptr<Expression> ParseBinaryOperator(Tokenizer* tokenizer, ArgParser arg_parser) {
    auto left = arg_parser(tokenizer);

    if (tokenizer->IsEnd()) {
        return left;
    }

    auto token = tokenizer->GetToken();
    while (auto ptr = std::get_if<SymbolToken>(&token)) {
        static constexpr char kOps[]{Ops...};
        if (std::string_view{kOps, sizeof(kOps)}.find(ptr->symbol) == std::string_view::npos) {
            break;
        }

        tokenizer->Next();
        left = DispatchOperator(ptr->symbol, std::move(left), arg_parser(tokenizer));

        if (tokenizer->IsEnd()) {
            break;
        }
        token = tokenizer->GetToken();
    }

    return left;
}

inline std::unique_ptr<Expression> ParseMultiplicativeExpression(Tokenizer* tokenizer) {
    return ParseBinaryOperator<'*', '/'>(tokenizer, ParseUnaryExpression);
}

inline std::unique_ptr<Expression> ParseAdditiveExpression(Tokenizer* tokenizer) {
    return ParseBinaryOperator<'+', '-'>(tokenizer, ParseMultiplicativeExpression);
}

inline std::unique_ptr<Expression> ParseExpression(Tokenizer* tok) {
    return ParseAdditiveExpression(tok);
}

// main.cpp
#include <iostream>
#include <sstream>

bool Prompt(std::string_view prompt, std::string& line) {
    std::cout << prompt << std::flush;
    return !!std::getline(std::cin, line);
}

int main() {
    std::string line;
    while (Prompt(">>> ", line)) {
        std::stringstream ss{line};
        try {
            Tokenizer tok{&ss};
            int64_t res = ParseExpression(&tok)->Evaluate();
            std::cout << res << std::endl;
        } catch (const SyntaxError& e) {
            std::cout << "Syntax error: " << e.what() << std::endl;
        }
    }
    std::cout << std::endl;
}