Parser combinators with C++20.

parser.cpp

#include <cstring>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <variant>
#include <vector>

template <class T>
using Output = std::variant<T, std::runtime_error>;
using Input = std::string_view&;
template <class T>
using Parser = std::function<Output<T>(Input)>;

template <class T, class U>
Parser<std::tuple<T, U>> seq(Parser<T> first, Parser<U> second) {
    return [first, second](Input in) -> Output<std::tuple<T, U>> {
        auto const out1 = first(in);
        if (out1.index() == 1) {
            return {std::get<1>(out1)};
        }
        auto const out2 = second(in);
        if (out2.index() == 1) {
            return {std::get<1>(out2)};
        }
        return {std::make_tuple(std::get<T>(out1), std::get<U>(out2))};
    };
}

template <class T, class U>
Parser<std::variant<T, U>> alt(Parser<T> first, Parser<U> second) {
    return [first, second](Input in) -> Output<std::variant<T, U>> {
        auto const out1 = first(in);
        if (out1.index() == 0) {
            return {std::variant<T, U>{std::in_place_index<0>, std::get<T>(out1)}};
        }
        auto const out2 = second(in);
        if (out2.index() == 0) {
            return {std::variant<T, U>{std::in_place_index<1>, std::get<U>(out2)}};
        }
        return {std::get<1>(out2)};
    };
}

template <class T>
Parser<std::vector<T>> repeat(Parser<T> parser) {
    return [parser](Input in) -> Output<std::vector<T>> {
        std::vector<T> ret;
        while (true) {
            auto const out = parser(in);
            if (out.index() == 1) {
                return {ret};
            }
            ret.push_back(std::get<T>(out));
        }
    };
}

template <char C>
Output<char> literal(Input in) {
    if (in.size() > 0 && in[0] == C) {
        in.remove_prefix(1);
        return {C};
    }
    return {std::runtime_error("literal unmatched")};
}

Output<int> num(Input in) {
    if (in.size() == 0 || !('0' <= in[0] && in[0] <= '9')) {
        return {std::runtime_error("no digits")};
    }
    int ret = 0;
    size_t used = 0;
    for (auto const ch : in) {
        if (!('0' <= ch && ch <= '9')) {
            break;
        }
        ++used;
        ret *= 10;
        ret += ch - '0';
    }
    in.remove_prefix(used);
    return ret;
}

Output<int> add_sub(Input in);

Output<int> term(Input in) {
    const auto parser = alt(
        seq(
            Parser<char>{&literal<'('>},
            seq(
                Parser<int>{&add_sub},
                Parser<char>{&literal<')'>}
            )
        ),
        Parser<int>{&num}
    );
    const auto output = parser(in);
    if (output.index() == 1) {
        return {std::get<1>(output)};
    }

    auto const choice = std::get<0>(output);
    if (choice.index() == 0) {
        auto const [_l, right] = std::get<0>(choice);
        auto const [num, _r] = right;
        return {num};
    }
    return {std::get<1>(choice)};
}

Output<int> mul_div(Input in) {
    const auto parser = seq(
        Parser<int>{&term},
        repeat(seq(
            alt(Parser<char>{&literal<'*'>}, Parser<char>{&literal<'/'>}),
            Parser<int>{&term}
        ))
    );
    const auto output = parser(in);
    if (output.index() == 1) {
        return {std::get<1>(output)};
    }

    auto const [lhs, rhs_items] = std::get<0>(output);
    int result = lhs;
    for (auto const & [op, rhs] : rhs_items) {
        if (op.index() == 0) {
            result *= rhs;
        } else {
            result /= rhs;
        }
    }
    return {result};
}

Output<int> add_sub(Input in) {
    const auto parser = seq(
        Parser<int>{&mul_div},
        repeat(seq(
            alt(Parser<char>{&literal<'+'>}, Parser<char>{&literal<'-'>}),
            Parser<int>{&mul_div}
        ))
    );
    const auto output = parser(in);
    if (output.index() == 1) {
        return {std::get<1>(output)};
    }

    auto const [lhs, rhs_items] = std::get<0>(output);
    int result = lhs;
    for (auto const & [op, rhs] : rhs_items) {
        if (op.index() == 0) {
            result += rhs;
        } else {
            result -= rhs;
        }
    }
    return {result};
}

Output<int> parse(Input in) {
    return add_sub(in);
}

int main() {
    std::string buf;
    std::cin >> buf;

    std::string_view slice{buf.c_str()};
    auto const result = parse(slice);

    if (result.index() == 0) {
        std::cout << std::get<int>(result) << "\n";
    } else {
        std::cerr << std::get<std::runtime_error>(result).what() << "\n";
    }
}