monadic_parser.cpp

#include <iostream>
#include <vector>
#include <optional>
#include <functional>
#include <cctype>

using namespace std;

struct unit {

};

template <typename A>
using Parser = function<optional<pair<A, string>>(string)>;

template <typename A>
optional<pair<A, string>> parse(Parser<A> p, string s) {
	return p(s);
}

template <typename A>
Parser<A> _return(A v) {
	return [=](string inp) {
		return make_pair(v, inp);
	};
}

template <typename A>
Parser<A> failure() {
	return [](string inp) {
		return nullopt;
	};
}

Parser<char> item() {
	return [](string inp) -> optional<pair<char, string>> {
		if (inp == "") {
			return nullopt;
		} else {
			return make_pair(inp[0], inp.substr(1));
		}
	};
}

template <typename A, typename B>
Parser<B> then(Parser<A> p, function<Parser<B>(A)> f) {
	return [=](string inp) -> optional<pair<B, string>> {
		auto r = parse(p, inp);
		if (r.has_value()) {
			auto [v, out] = *r;
			return parse(f(v), out);
		} else {
			return nullopt;
		}
	};
}

template <typename A>
Parser<A> or_else(Parser<A> p, Parser<A> q) {
	return [=](string inp) {
		auto r = parse(p, inp);
		if (r.has_value()) {
			return r;
		} else {
			return parse(q, inp);
		}
	};
}

Parser<char> sat(function<bool(char)> p) {
	return then<char, char>(item(), [=](char x) {
		return p(x) ? _return(x) : failure<char>();
	});
}

Parser<char> digit() {
	return sat([](char c) { return isdigit(c); });
}

Parser<char> lower() {
	return sat([](char c) { return islower(c); });
}

Parser<char> upper() {
	return sat([](char c) { return isupper(c); });
}

Parser<char> letter() {
	return sat([](char c) { return isalpha(c); });
}

Parser<char> alphanum() {
	return sat([](char c) { return isalnum(c); });
}

Parser<char> _char(char x) {
	return sat([=](char c) { return x == c; });
}

Parser<string> _string(string inp) {
	if (inp == "") {
		return _return("");
	} else {
		char x = inp[0];
		string xs = inp.substr(1);
		return then<char, string>(_char(x), [=](char) {
			return then<string, string>(_string(xs), [=](string) {
				return _return(x + xs);
			});
		});
	}
}

template <typename A>
Parser<vector<A>> many(Parser<A> p);

template <typename A>
Parser<vector<A>> many1(Parser<A> p);

template <typename A>
Parser<vector<A>> many(Parser<A> p) {
	return or_else(many1(p), _return(vector<A> {}));
}

template <typename A>
Parser<vector<A>> many1(Parser<A> p) {
	return then<A, vector<A>>(p, [=](A v) {
		return then<vector<A>, vector<A>>(many(p), [=](vector<A> vs) {
			vector<A> r = vs;
			r.insert(r.begin(), v);
			return _return(r);
		});
	});
}

Parser<string> ident() {
	return then<char, string>(lower(), [](char x) {
		return then<vector<char>, string>(many(alphanum()), [=](vector<char> xs) {
			string s(xs.begin(), xs.end());
			s.insert(s.begin(), x);
			return _return(s);
		});
	});
}

Parser<int> nat() {
	return then<vector<char>, int>(many1(digit()), [](vector<char> xs) {
		string s(xs.begin(), xs.end());
		return _return(stoi(s));
	});
}

Parser<unit> space() {
	return then<vector<char>, unit>(many(sat([](char c) { return isspace(c); })), [](vector<char>) {
		return _return(unit {});
	});
}

template <typename A>
Parser<A> token(Parser<A> p) {
	return then<unit, A>(space(), [=](unit) {
		return then<A, A>(p, [=](A v) {
			return then<unit, A>(space(), [=](unit) {
				return _return(v);
			});
		});
	});
}

Parser<string> identifier() {
	return token(ident());
}

Parser<int> natural() {
	return token(nat());
}

Parser<string> symbol(string xs) {
	return token(_string(xs));
}

Parser<int> expr();
Parser<int> term();
Parser<int> factor();

Parser<int> expr() {
	return then<int, int>(term(), [](int t) {
		return or_else(then<string, int>(symbol("+"), [=](string) {
			return then<int, int>(expr(), [=](int e) {
				return _return(t + e);
			});
		}), _return(t));
	});
}

Parser<int> term() {
	return then<int, int>(factor(), [](int f) {
		return or_else(then<string, int>(symbol("*"), [=](string) {
			return then<int, int>(term(), [=](int t) {
				return _return(f * t);
			});
		}), _return(f));
	});
}

Parser<int> factor() {
	return or_else(then<string, int>(symbol("("), [](string) {
		return then<int, int>(expr(), [](int e) {
			return then<string, int>(symbol(")"), [=](string) {
				return _return(e);
			});
		});
	}), natural());
}

int eval(string xs) {
	auto r = parse(expr(), xs);
	if (r.has_value()) {
		auto [n, out] = *r;
		if (out == "") {
			return n;
		}
		throw runtime_error("Unused input");
	} else {
		throw runtime_error("Invalid input");
	}
}

int main(int argc, char** argv) {
	// auto p = then<string, vector<int>>(symbol("["), [](string) {
	//     return then<int, vector<int>>(natural(), [](int n) {
	//         return then<vector<int>, vector<int>>(many<int>(then<string, int>(symbol(","), [](string) {
	//             return natural();
	//         })), [=](vector<int> ns) {
	//             return then<string, vector<int>>(symbol("]"), [=](string) {
	//                 vector r = ns;
	//                 r.insert(r.begin(), n);
	//                 return _return(r);
	//             });
	//         });
	//     });
	// });

	// auto [xs, s] = *parse(p, "[1, 2, 3]");
	// for (auto x : xs) {
	//     cout << x << " ";
	// }
	// cout << endl;

	while (true) {
		string s;
		std::getline(cin, s);

		int n = eval(s);
		cout << n << endl;
	}

	return 0;
}