#include template class TD; template constexpr bool is_in_list = (std::is_same_v || ...); template struct variant_concat; template struct variant_concat> { using type = std::variant; }; template struct unique_variant { using type = std::conditional_t< is_in_list, typename unique_variant::type, typename variant_concat::type>::type >; }; template struct unique_variant { using type = std::variant; }; template using unique_variant_t = typename unique_variant::type; template class optional : std::optional { public: optional() : std::optional() {} template optional(Q&& v) : std::optional(std::forward(v)) {} using std::optional::has_value; using std::optional::value; using std::optional::value_or; using std::optional::operator bool; template> auto map(F&& f) { // f: T => ? if (!has_value()) return optional(); return optional(f(value())); } template> auto flat_map(F&& f) { // f : T => optional if (!has_value()) return Q(); return f(value()); } auto or_else(const optional& alternative) { if (!has_value()) return alternative; return *this; } }; template using ParseResult = optional; template using Parser = std::function(std::string_view&)>; template> Parser operator % (const Parser& p, F&& f) { return [=](std::string_view& in)->ParseResult { return p(in).map([&](T v) { return f(v); }); }; } template> Parser operator % (const Parser>& p, F&& f) { return [=](std::string_view& in)->ParseResult { return p(in).map([&](auto v) { return std::apply(f, v); }); }; } #define RESOLVE_OVERLOAD(...) \ [](auto&&...args)->decltype(auto){return __VA_ARGS__(std::forward(args)...);} Parser literal(const std::string& s) { return [=](std::string_view& in)->ParseResult { if (in.starts_with(s)) { in.remove_prefix(s.length()); return s; } else { return {}; } }; } Parser> seq() { return [](std::string_view&)->ParseResult> { return std::make_tuple(); }; } template> Parser seq(const Parser& p, const Parser& ...ps) { return [=](std::string_view& in)->ParseResult { return p(in).flat_map([&](auto v) { return seq(ps...)(in).map([&](auto vs) { return std::tuple_cat(std::make_tuple(v), vs); }); }); }; } template Parser attempt(const Parser& p) { return [=](std::string_view& in)->ParseResult { auto in_bak = in; auto v = p(in); if (!v) in = in_bak; return v; }; } namespace detail { template Parser alt() { return [](std::string_view&)->ParseResult { return {}; }; } template Parser alt(const Parser& p, const Parser& ...ps) { return [=](std::string_view& in)->ParseResult { return attempt(p)(in).map([](auto v){ return R{v}; }) .or_else(alt(ps...)(in)); }; } template auto flat(const std::variant& v) { if constexpr (sizeof...(Ts) == 1) { return std::get<0>(v); } else { return v; } } } template auto alt(const Parser& ...ps) { return detail::alt>(ps...) % RESOLVE_OVERLOAD(detail::flat); } template> Parser many(const Parser& p) { return [=](std::string_view& in)->ParseResult { R r; ParseResult v; while ((v = attempt(p)(in))) { r.emplace_back(v.value()); } return r; }; } template Parser ch(const std::function& f) { return [=](std::string_view& in)->ParseResult { if (in.empty() || !f(in[0])) return {}; char c = in[0]; in.remove_prefix(1); return c; }; } template Parser lazy(const Parser& p) { return [p_addr = &p](std::string_view& in)->ParseResult { return (*p_addr)(in); }; } int main() { auto eval = [](int a, std::string op, int b) { if (op == "*") return a * b; if (op == "/") return a / b; if (op == "+") return a + b; if (op == "-") return a - b; assert(0); }; Parser exp; Parser number = many(ch(isdigit)) % [](std::vector v) { int r = 0; for (char c: v) r = r * 10 + c - '0'; return r; }; Parser factor = alt( seq(literal("("), lazy(exp), literal(")")) % [](auto x){ return std::get<1>(x); }, number ); Parser term = alt( seq(factor, literal("*"), factor) % eval, seq(factor, literal("/"), factor) % eval, factor ); exp = alt( seq(term, literal("+"), term) % eval, seq(term, literal("-"), term) % eval, term ); std::string_view in = "4+(1+2)*3"; std::cout << exp(in).value() << std::endl; }