472 lines
19 KiB
C++
472 lines
19 KiB
C++
#include <iomanip>
|
|
#include <iostream>
|
|
#include <optional>
|
|
#include <variant>
|
|
#include <cassert>
|
|
#include <string>
|
|
#include <memory>
|
|
#include <queue>
|
|
#include <stack>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include "container.hpp"
|
|
#include "slice.hpp"
|
|
#ifndef USE_GMP
|
|
#include "bigint_nat.hpp" // native big integer
|
|
#else
|
|
#include "bigint_gmp.hpp" // GNU MP big integer
|
|
#endif
|
|
#if defined _WIN32
|
|
#include <Windows.h>
|
|
#elif defined __unix__
|
|
#include <unistd.h>
|
|
#include <signal.h>
|
|
#include <sys/resource.h>
|
|
#endif
|
|
#ifndef STACK_SIZE
|
|
#define STACK_SIZE 8388608 // 8 MiB
|
|
#endif
|
|
char *stack_top;
|
|
char *stack_cur;
|
|
void ini_stack() {
|
|
char dummy;
|
|
stack_top = &dummy;
|
|
}
|
|
bool chk_stack() {
|
|
char dummy;
|
|
stack_cur = &dummy;
|
|
return stack_top - stack_cur >= STACK_SIZE / 2;
|
|
}
|
|
#if defined _WIN32
|
|
void clr_flag() {
|
|
GetAsyncKeyState(VK_ESCAPE);
|
|
}
|
|
bool chk_flag() {
|
|
return GetAsyncKeyState(VK_ESCAPE) & 0x0001;
|
|
}
|
|
#elif defined __unix__
|
|
bool flag_rec;
|
|
void set_flag(int) {
|
|
flag_rec = 1;
|
|
}
|
|
void clr_flag() {
|
|
flag_rec = 0;
|
|
}
|
|
bool chk_flag() {
|
|
return flag_rec;
|
|
}
|
|
#endif
|
|
auto read(Slice &exp) {
|
|
auto i = exp.get_beg();
|
|
auto n = exp.get_end();
|
|
for (;; i++) {
|
|
if (i == n) {
|
|
return exp.reset_to(i, n), exp.from_to(i, i);
|
|
} else if (*i != ' ') {
|
|
break;
|
|
}
|
|
}
|
|
auto j = i;
|
|
auto c = 0;
|
|
for (;; i++) {
|
|
if ((i == n || *i == ' ') && c == 0) {
|
|
return exp.reset_to(i, n), exp.from_to(j, i);
|
|
} else if (i == n) {
|
|
throw std::runtime_error("mismatched parentheses");
|
|
} else if (*i == '(') {
|
|
c++;
|
|
} else if (*i == ')') {
|
|
c--;
|
|
}
|
|
}
|
|
}
|
|
BigInt operator+(BigInt const &lval, BigInt const &rval);
|
|
BigInt operator-(BigInt const &lval, BigInt const &rval);
|
|
BigInt operator*(BigInt const &lval, BigInt const &rval);
|
|
BigInt operator/(BigInt const &lval, BigInt const &rval);
|
|
BigInt operator%(BigInt const &lval, BigInt const &rval);
|
|
bool operator>(BigInt const &lval, BigInt const &rval);
|
|
bool operator<(BigInt const &lval, BigInt const &rval);
|
|
bool operator>=(BigInt const &lval, BigInt const &rval);
|
|
bool operator<=(BigInt const &lval, BigInt const &rval);
|
|
bool operator==(BigInt const &lval, BigInt const &rval);
|
|
bool operator!=(BigInt const &lval, BigInt const &rval);
|
|
typedef BigInt (*opr_t)(BigInt const &, BigInt const &);
|
|
typedef bool (*cmp_t)(BigInt const &, BigInt const &);
|
|
static inline std::unordered_map<char, opr_t> const oprs = {
|
|
{'+', operator+},
|
|
{'-', operator-},
|
|
{'*', operator*},
|
|
{'/', operator/},
|
|
{'%', operator%},
|
|
};
|
|
static inline std::unordered_map<char, cmp_t> const cmps = {
|
|
{'>', operator>},
|
|
{'<', operator<},
|
|
{'=', operator==},
|
|
};
|
|
class Tree {
|
|
enum TokenIdx: std::size_t {
|
|
Und,
|
|
Nil, Chk,
|
|
Par, Int,
|
|
Opr, AOI,
|
|
Cmp, ACI,
|
|
LEF, EEF, // Lazy/Eager-Evaluation Function
|
|
App, Arg,
|
|
};
|
|
using TokenVar = std::variant<
|
|
std::nullopt_t,
|
|
std::monostate, std::monostate,
|
|
std::string, BigInt,
|
|
std::pair<char, opr_t>, std::pair<std::pair<char, opr_t>, BigInt>,
|
|
std::pair<char, cmp_t>, std::pair<std::pair<char, cmp_t>, BigInt>,
|
|
Box<std::pair<std::string, Tree>>, Box<std::pair<std::string, Tree>>,
|
|
Box<std::pair<Tree, Tree>>, std::shared_ptr<std::pair<Tree, bool>>>;
|
|
TokenVar token;
|
|
template <typename... Args, typename = std::enable_if_t<std::is_constructible_v<TokenVar, Args &&...>>>
|
|
Tree(Args &&...args): token(std::forward<Args>(args)...) {}
|
|
static Tree first(Tree &&fst) {
|
|
if (fst.token.index() == TokenIdx::Und) {
|
|
throw std::runtime_error("empty expression");
|
|
} else {
|
|
return std::move(fst);
|
|
}
|
|
}
|
|
static Tree build(Tree &&fst, Tree &&snd) {
|
|
if (fst.token.index() == TokenIdx::Und) {
|
|
return std::move(snd);
|
|
} else {
|
|
return Box<std::pair<Tree, Tree>>::make(std::move(fst), std::move(snd));
|
|
}
|
|
}
|
|
static Tree parse(Slice &&exp, Tree &&fun = std::nullopt, Tree &&fst = std::nullopt) {
|
|
if (auto sym = read(exp); sym.empty()) {
|
|
return build(std::move(fun), first(std::move(fst)));
|
|
} else if (sym[0] == '\\') {
|
|
return build(std::move(fun), build(std::move(fst), Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make(sym(1, 0), parse(std::move(exp))))));
|
|
} else if (sym[0] == '|') {
|
|
return parse(std::move(exp), Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make(sym(1, 0), build(std::move(fun), first(std::move(fst))))));
|
|
} else if (sym[0] == '^') {
|
|
return build(std::move(fun), build(std::move(fst), Tree(std::in_place_index<TokenIdx::EEF>, Box<std::pair<std::string, Tree>>::make(sym(1, 0), parse(std::move(exp))))));
|
|
} else if (sym[0] == '@') {
|
|
return parse(std::move(exp), Tree(std::in_place_index<TokenIdx::EEF>, Box<std::pair<std::string, Tree>>::make(sym(1, 0), build(std::move(fun), first(std::move(fst))))));
|
|
} else {
|
|
return parse(std::move(exp), std::move(fun), build(std::move(fst), lex(std::move(sym))));
|
|
}
|
|
}
|
|
static Tree lex(Slice const &sym) {
|
|
if (sym[0] == '(' && sym[-1] == ')') {
|
|
return parse(sym(1, -1));
|
|
} else if (sym[0] == '$') {
|
|
return Tree(std::in_place_index<TokenIdx::Par>, sym(1, 0));
|
|
} else if (sym.size() == 3 && sym == "...") {
|
|
return Tree(std::in_place_index<TokenIdx::Nil>);
|
|
} else if (sym.size() == 1 && sym == "?") {
|
|
return Tree(std::in_place_index<TokenIdx::Chk>);
|
|
} else if (auto const &o = oprs.find(sym[0]); sym.size() == 1 && o != oprs.end()) {
|
|
return Tree(std::in_place_index<TokenIdx::Opr>, *o);
|
|
} else if (auto const &c = cmps.find(sym[0]); sym.size() == 1 && c != cmps.end()) {
|
|
return Tree(std::in_place_index<TokenIdx::Cmp>, *c);
|
|
} else try {
|
|
return Tree(std::in_place_index<TokenIdx::Int>, BigInt::from_string(sym));
|
|
} catch (...) {
|
|
throw std::runtime_error("invalid symbol: " + std::string(sym));
|
|
}
|
|
}
|
|
void calc() {
|
|
static const auto T = Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make("T", Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make("F", Tree(std::in_place_index<TokenIdx::Par>, "T")))));
|
|
static const auto F = Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make("T", Tree(std::in_place_index<TokenIdx::LEF>, Box<std::pair<std::string, Tree>>::make("F", Tree(std::in_place_index<TokenIdx::Par>, "F")))));
|
|
if (chk_stack()) {
|
|
throw std::runtime_error("recursion limit exceeded");
|
|
}
|
|
tail_call:
|
|
if (chk_flag()) {
|
|
throw std::runtime_error("keyboard interrupt");
|
|
}
|
|
if (auto papp = std::get_if<TokenIdx::App>(&token)) {
|
|
auto &[fst, snd] = **papp;
|
|
fst.calc();
|
|
if (auto pnil = std::get_if<TokenIdx::Nil>(&fst.token)) {
|
|
token.emplace<TokenIdx::Nil>();
|
|
} else if (auto pchk = std::get_if<TokenIdx::Chk>(&fst.token)) {
|
|
snd.calc();
|
|
*this = snd.token.index() == TokenIdx::Nil ? F : T;
|
|
} else if (auto plef = std::get_if<TokenIdx::LEF>(&fst.token)) {
|
|
auto &[par, tmp] = **plef;
|
|
tmp.substitute(std::make_shared<std::pair<Tree, bool>>(std::move(snd), 0), std::move(par));
|
|
*this = Tree(std::move(tmp));
|
|
goto tail_call;
|
|
} else if (auto peef = std::get_if<TokenIdx::EEF>(&fst.token)) {
|
|
snd.calc();
|
|
auto &[par, tmp] = **peef;
|
|
tmp.substitute(std::make_shared<std::pair<Tree, bool>>(std::move(snd), 1), std::move(par));
|
|
*this = Tree(std::move(tmp));
|
|
goto tail_call;
|
|
} else if (auto popr = std::get_if<TokenIdx::Opr>(&fst.token)) {
|
|
snd.calc();
|
|
if (auto pint = std::get_if<TokenIdx::Int>(&snd.token); pint && (*pint || popr->first != '/' && popr->first != '%')) {
|
|
token = std::make_pair(std::move(*popr), std::move(*pint));
|
|
} else if (auto pnil = std::get_if<TokenIdx::Nil>(&snd.token)) {
|
|
token.emplace<TokenIdx::Nil>();
|
|
} else {
|
|
throw std::runtime_error("cannot apply " + fst.translate() + " on: " + snd.translate());
|
|
}
|
|
} else if (auto pcmp = std::get_if<TokenIdx::Cmp>(&fst.token)) {
|
|
snd.calc();
|
|
if (auto pint = std::get_if<TokenIdx::Int>(&snd.token)) {
|
|
token = std::make_pair(std::move(*pcmp), std::move(*pint));
|
|
} else if (auto pnil = std::get_if<TokenIdx::Nil>(&snd.token)) {
|
|
token.emplace<TokenIdx::Nil>();
|
|
} else {
|
|
throw std::runtime_error("cannot apply " + fst.translate() + " on: " + snd.translate());
|
|
}
|
|
} else if (auto paoi = std::get_if<TokenIdx::AOI>(&fst.token)) {
|
|
snd.calc();
|
|
if (auto pint = std::get_if<TokenIdx::Int>(&snd.token)) {
|
|
token = paoi->first.second(std::move(*pint), std::move(paoi->second));
|
|
} else if (auto pnil = std::get_if<TokenIdx::Nil>(&snd.token)) {
|
|
token.emplace<TokenIdx::Nil>();
|
|
} else {
|
|
throw std::runtime_error("cannot apply " + fst.translate() + " on: " + snd.translate());
|
|
}
|
|
} else if (auto paci = std::get_if<TokenIdx::ACI>(&fst.token)) {
|
|
snd.calc();
|
|
if (auto pint = std::get_if<TokenIdx::Int>(&snd.token)) {
|
|
*this = paci->first.second(std::move(*pint), std::move(paci->second)) ? T : F;
|
|
} else if (auto pnil = std::get_if<TokenIdx::Nil>(&snd.token)) {
|
|
token.emplace<TokenIdx::Nil>();
|
|
} else {
|
|
throw std::runtime_error("cannot apply " + fst.translate() + " on: " + snd.translate());
|
|
}
|
|
} else {
|
|
throw std::runtime_error("invalid function: " + fst.translate());
|
|
}
|
|
} else if (auto parg = std::get_if<TokenIdx::Arg>(&token)) {
|
|
auto &shr = (*parg)->first;
|
|
auto rec = (*parg)->second;
|
|
if (parg->use_count() == 1) {
|
|
*this = Tree(std::move(shr));
|
|
if (not rec) {
|
|
goto tail_call;
|
|
}
|
|
} else {
|
|
if (not rec) {
|
|
shr.calc();
|
|
rec = true;
|
|
}
|
|
*this = shr;
|
|
}
|
|
}
|
|
}
|
|
void substitute(std::shared_ptr<std::pair<Tree, bool>> const &arg, std::string const &tar) {
|
|
if (auto papp = std::get_if<TokenIdx::App>(&token)) {
|
|
auto &[fst, snd] = **papp;
|
|
fst.substitute(arg, tar);
|
|
snd.substitute(arg, tar);
|
|
} else if (auto plef = std::get_if<TokenIdx::LEF>(&token)) {
|
|
auto &[par, tmp] = **plef;
|
|
if (par != tar) {
|
|
tmp.substitute(arg, tar);
|
|
}
|
|
} else if (auto peef = std::get_if<TokenIdx::EEF>(&token)) {
|
|
auto &[par, tmp] = **peef;
|
|
if (par != tar) {
|
|
tmp.substitute(arg, tar);
|
|
}
|
|
} else if (auto ppar = std::get_if<TokenIdx::Par>(&token)) {
|
|
if (*ppar == tar) {
|
|
token.emplace<TokenIdx::Arg>(arg);
|
|
}
|
|
}
|
|
}
|
|
void analyze(std::unordered_set<std::string> &set) {
|
|
if (auto papp = std::get_if<TokenIdx::App>(&token)) {
|
|
auto &[fst, snd] = **papp;
|
|
fst.analyze(set);
|
|
snd.analyze(set);
|
|
} else if (auto plef = std::get_if<TokenIdx::LEF>(&token)) {
|
|
auto &[par, tmp] = **plef;
|
|
if (set.find(par) != set.end()) {
|
|
tmp.analyze(set);
|
|
} else {
|
|
auto pos = set.insert(par).first;
|
|
tmp.analyze(set);
|
|
set.erase(pos);
|
|
}
|
|
} else if (auto peef = std::get_if<TokenIdx::EEF>(&token)) {
|
|
auto &[par, tmp] = **peef;
|
|
if (set.find(par) != set.end()) {
|
|
tmp.analyze(set);
|
|
} else {
|
|
auto pos = set.insert(par).first;
|
|
tmp.analyze(set);
|
|
set.erase(pos);
|
|
}
|
|
} else if (auto ppar = std::get_if<TokenIdx::Par>(&token)) {
|
|
if (set.find(*ppar) == set.end()) {
|
|
if (auto const &itr = map.find(*ppar); itr != map.end()) {
|
|
token.emplace<TokenIdx::Arg>(itr->second);
|
|
} else {
|
|
throw std::runtime_error("unbound variable: $" + *ppar);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
static inline std::unordered_map<std::string, std::shared_ptr<std::pair<Tree, bool>>> map;
|
|
public:
|
|
Tree(Tree const &other): token(other.token) {}
|
|
Tree &operator=(Tree const &other) {
|
|
token = other.token;
|
|
return *this;
|
|
}
|
|
Tree(Tree &&other): token(std::exchange(other.token, std::nullopt)) {}
|
|
Tree &operator=(Tree &&other) {
|
|
token = std::exchange(other.token, std::nullopt);
|
|
return *this;
|
|
}
|
|
~Tree() {
|
|
if (token.index() == TokenIdx::Und) {
|
|
return;
|
|
}
|
|
std::queue<TokenVar> flat;
|
|
flat.push(std::exchange(token, std::nullopt));
|
|
for (; not flat.empty(); flat.pop()) {
|
|
auto &token = flat.front();
|
|
if (auto papp = std::get_if<TokenIdx::App>(&token)) {
|
|
auto &[fst, snd] = **papp;
|
|
flat.push(std::exchange(fst.token, std::nullopt));
|
|
flat.push(std::exchange(snd.token, std::nullopt));
|
|
} else if (auto parg = std::get_if<TokenIdx::LEF>(&token)) {
|
|
auto &[par, tmp] = **parg;
|
|
flat.push(std::exchange(tmp.token, std::nullopt));
|
|
} else if (auto parg = std::get_if<TokenIdx::EEF>(&token)) {
|
|
auto &[par, tmp] = **parg;
|
|
flat.push(std::exchange(tmp.token, std::nullopt));
|
|
} else if (auto parg = std::get_if<TokenIdx::Arg>(&token)) {
|
|
auto &shr = (*parg)->first;
|
|
if (parg->use_count() == 1) {
|
|
flat.push(std::exchange(shr.token, std::nullopt));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
static auto const &put(Slice &&exp, std::string const &par, bool calc) {
|
|
auto res = parse(std::move(exp));
|
|
std::unordered_set<std::string> set;
|
|
res.analyze(set);
|
|
map.erase(par);
|
|
if (calc) {
|
|
clr_flag();
|
|
res.calc();
|
|
}
|
|
return map.emplace(par, std::make_shared<std::pair<Tree, bool>>(std::move(res), calc)).first->second->first;
|
|
}
|
|
static auto const &dir() {
|
|
return map;
|
|
}
|
|
static void clr() {
|
|
return map.clear();
|
|
}
|
|
std::string translate(bool lb = 0, bool rb = 0) const {
|
|
if (auto pnil = std::get_if<TokenIdx::Nil>(&token)) {
|
|
return "...";
|
|
} else if (auto pchk = std::get_if<TokenIdx::Chk>(&token)) {
|
|
return "?";
|
|
} else if (auto plef = std::get_if<TokenIdx::LEF>(&token)) {
|
|
auto &[par, tmp] = **plef;
|
|
auto s = "\\" + par + " " + tmp.translate(0, rb && !rb);
|
|
return rb ? "(" + s + ")" : s;
|
|
} else if (auto peef = std::get_if<TokenIdx::EEF>(&token)) {
|
|
auto &[par, tmp] = **peef;
|
|
auto s = "^" + par + " " + tmp.translate(0, rb && !rb);
|
|
return rb ? "(" + s + ")" : s;
|
|
} else if (auto pint = std::get_if<TokenIdx::Int>(&token)) {
|
|
return pint->to_string();
|
|
} else if (auto popr = std::get_if<TokenIdx::Opr>(&token)) {
|
|
return std::string{popr->first};
|
|
} else if (auto pcmp = std::get_if<TokenIdx::Cmp>(&token)) {
|
|
return std::string{pcmp->first};
|
|
} else if (auto paoi = std::get_if<TokenIdx::AOI>(&token)) {
|
|
auto s = std::string{paoi->first.first, ' '} + paoi->second.to_string();
|
|
return lb ? "(" + s + ")" : s;
|
|
} else if (auto paci = std::get_if<TokenIdx::ACI>(&token)) {
|
|
auto s = std::string{paci->first.first, ' '} + paci->second.to_string();
|
|
return lb ? "(" + s + ")" : s;
|
|
} else if (auto papp = std::get_if<TokenIdx::App>(&token)) {
|
|
auto &[fst, snd] = **papp;
|
|
auto s = fst.translate(lb && !lb, 1) + " " + snd.translate(1, rb && !lb);
|
|
return lb ? "(" + s + ")" : s;
|
|
} else if (auto parg = std::get_if<TokenIdx::Arg>(&token)) {
|
|
return (*parg)->first.translate(lb, rb);
|
|
} else if (auto ppar = std::get_if<TokenIdx::Par>(&token)) {
|
|
return "$" + *ppar;
|
|
} else {
|
|
assert(false); // unreachable
|
|
}
|
|
}
|
|
};
|
|
int main(int argc, char *argv[]) {
|
|
ini_stack();
|
|
bool check_stdin = false;
|
|
bool check_stdout = false;
|
|
bool check_stderr = false;
|
|
#if defined _WIN32
|
|
DWORD dwModeTemp;
|
|
check_stdin = GetConsoleMode(GetStdHandle(STD_INPUT_HANDLE), &dwModeTemp);
|
|
check_stdout = GetConsoleMode(GetStdHandle(STD_OUTPUT_HANDLE), &dwModeTemp);
|
|
check_stderr = GetConsoleMode(GetStdHandle(STD_ERROR_HANDLE), &dwModeTemp);
|
|
#elif defined __unix__
|
|
check_stdin = isatty(fileno(stdin));
|
|
check_stdout = isatty(fileno(stdout));
|
|
check_stderr = isatty(fileno(stderr));
|
|
struct rlimit rlim;
|
|
getrlimit(RLIMIT_STACK, &rlim);
|
|
rlim.rlim_cur = STACK_SIZE;
|
|
setrlimit(RLIMIT_STACK, &rlim);
|
|
struct sigaction act;
|
|
act.sa_handler = set_flag;
|
|
sigemptyset(&act.sa_mask);
|
|
act.sa_flags = 0; // use SA_RESTART to avoid getting EOF when SIGINT is received during input
|
|
sigaction(SIGINT, &act, NULL);
|
|
#endif
|
|
std::string ps_in = check_stderr && check_stdin ? ">> " : "";
|
|
std::string ps_out = check_stderr && check_stdout ? "=> " : "";
|
|
std::string ps_res = check_stderr && check_stdout ? "== " : "";
|
|
for (bool end = false; not end;) {
|
|
std::cerr << ps_in;
|
|
Slice exp = Slice::getline(std::cin);
|
|
if (std::cin.eof()) {
|
|
end = true;
|
|
if (check_stderr && check_stdin) {
|
|
std::cerr << std::endl;
|
|
}
|
|
}
|
|
try {
|
|
if (auto cmd = read(exp); cmd.empty() || cmd.size() == 1 && cmd == "#") {
|
|
continue;
|
|
} else if (cmd[0] == ':') {
|
|
Tree::put(std::move(exp), cmd(1, 0), 0);
|
|
} else if (cmd.size() == 3 && cmd == "cal") {
|
|
auto &res = Tree::put(std::move(exp), "", 1);
|
|
std::cerr << ps_res;
|
|
std::cout << res.translate() << std::endl;
|
|
} else if (cmd.size() == 3 && cmd == "dir") {
|
|
for (auto &[par, arg] : Tree::dir()) {
|
|
std::cerr << ps_out;
|
|
std::cout << ":" + par << std::endl;
|
|
}
|
|
} else if (cmd.size() == 3 && cmd == "clr") {
|
|
Tree::clr();
|
|
} else if (cmd.size() == 3 && cmd == "end") {
|
|
end = true;
|
|
} else {
|
|
throw std::runtime_error("unknown command: " + std::string(cmd));
|
|
}
|
|
} catch (std::exception const &e) {
|
|
std::cerr << "Runtime Error: " << e.what() << std::endl;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|