#278858 (C++17) No.46 はじめのn歩

• 問題: No.46 はじめのn歩
• ユーザー: shibh308
• 提出日時: 2018-08-18 11:52:13
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 25,133 bytes
• コンパイル時間: 4,729 ms
• コンパイル使用メモリ: 273,736 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-14 14:18:41
• 合計ジャッジ時間: 5,109 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	2 ms; 6,820 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	2 ms; 6,820 KB
testcase_09	AC	1 ms; 6,816 KB

ソースコード

#include <bits/stdc++.h>
#include <variant>

#define USE_CIN

#define DO_EVAL

typedef std::variant<int, bool> body_type;
typedef std::variant<std::function<void(body_type&)>, std::function<void(std::vector<std::reference_wrapper<body_type>>)>> eval_func;

const char LAMBDA = '@';
const char SPACE = ' ';
const char OPEN = '(';
const char CLOSE = ')';
const char DOT = '.';
const char COMMA = ',';
const char COLON = ':';

const char AT = '&';
const char LT = '$'; // LT

const int OUT_INDENT = 4;

const int PARENT = -1;
const int VALUE = 0;
const int ABST = 1;
const int APPLY = 2;
const int TYPE = 3;
const int TARGET = 4;
const int FUNC = 5; // 他で明示的に指定されてるもの
const int TUPLE = 6;
const int ACCESS = 7;
const int LET = 8;

const std::string BOOL = "B";
const std::string TRUE = "true";
const std::string FALSE = "false";

const int BOOL_INT = 0;
const int NAT_INT = 1;
const int TUPLE_INT = 2;
const int VARIABLE_INT = -1; // 変数

const std::string NAT = "N";

const int MAX = 1e9+7;

#ifdef DO_OUTPUT
std::ofstream of("output.json");
#endif

auto type_value_to_str = [](int val){

	if(val == BOOL_INT)
		return "bool";
	if(val == NAT_INT)
		return "nat";
	if(val == TUPLE_INT)
		return "tuple";
	if(val == VARIABLE_INT)
		return "variable";

	return "not match";
};

auto type_to_str = [](int val){
	if(val == VALUE)
		return "value";
	else if(val == PARENT)
		return "parent";
	else if(val == ABST)
		return "abst";
	else if(val == APPLY)
		return "apply";
	else if(val == TYPE)
		return "type";
	else if(val == TARGET)
		return  "target";
	else if(val == TUPLE)
		return  "tuple";
	else if(val == ACCESS)
		return  "access";
	else if(val == LET)
		return  "let";
	else if(val == FUNC)
		return  "func";
	return "err";
};

auto is_nat = [](std::string& inp, int st, int en){
	// 先頭のマイナスは許容
	if(inp.at(st) == '-')
		++st;
	for(int index = st; index < en; ++index)
		if(!('0' <= inp.at(index) && inp.at(index) <= '9'))
			return false;
	return true;
};

auto is_val = [](std::string& inp, int st, int en){

	for(int index = st; index < en; ++index)
		if(!(('a' <= inp.at(index) && inp.at(index) <= 'z') ||
		   ('A' <= inp.at(index) && inp.at(index) <= 'Z')))
			return false;
	return true;
};

// inp[st,en)("type": value)がどのような型(bool, nat等)を取っているか
auto check_type = [](std::string& inp, int st, int en){
	std::string subst = inp.substr(st, en - st);
	if(subst == FALSE || subst == TRUE)
		return BOOL_INT;
	else if(is_nat(inp, st, en))
		return NAT_INT;
	else if(is_val(inp, st, en))
		return VARIABLE_INT;

	// matchしない場合
	return MAX;
};

auto match_type = [](std::string& inp, int st, int en){
	std::string subst = inp.substr(st, en - st);
	if(subst == BOOL)
		return BOOL_INT;
	if(subst == NAT)
		return NAT_INT;
	return MAX;
};

auto match = [](std::string& inp, int st, int en, char pattern, bool foward = true){
	if(foward)
		for(int index = st; index < en; ++index){
			if(inp.at(index) == pattern)
				return index;
		}
	else
		for(int index = en - 1; index >= st; --index)
			if(inp.at(index) == pattern)
				return index;

	return MAX;
};

auto match_nest = [](std::string& inp, int st, int en, char pattern){
	int nest = 0;
	for(int index = st; index < en; ++index){
		if(inp.at(index) == OPEN)
			++nest;
		else if(inp.at(index) == CLOSE)
			--nest;
		else if(!nest && inp.at(index) == pattern)
			return index;
		if(nest < 0)
			return -1;
	}
	return MAX;
};


struct Primitive{
	std::string name;
	int id, arg_type, ret_type;
	std::vector<int> tuple_types;
	eval_func func;
	Primitive(std::string name, int id, int arg_type, int ret_type, eval_func func, std::vector<int> tuple_types = std::vector<int>(0)) : 
		name(name),
		id(id),
		arg_type(arg_type),
		ret_type(ret_type),
		func(func),
		tuple_types(tuple_types)
	{
	}
};

std::vector<Primitive> prims;

void init(){

	std::function<void(body_type&)> succ = [](body_type& inp){
		++std::get<int>(inp);
	};
	prims.emplace_back("succ", 1, NAT_INT, NAT_INT, succ);

	std::function<void(body_type&)> pred = [](body_type& inp){
		--std::get<int>(inp);
	};
	prims.emplace_back("pred", 1, NAT_INT, NAT_INT, pred);

	std::function<void(body_type&)> any = [](body_type& inp){
		inp = static_cast<bool>(std::get<int>(inp) != 0);
	};
	prims.emplace_back("any", 1, NAT_INT, BOOL_INT, any);

	std::function<void(body_type&)> not_ = [](body_type& inp){
		inp = static_cast<bool>(std::get<bool>(inp) == 0);
	};
	prims.emplace_back("not", 1, BOOL_INT, BOOL_INT, not_);

	std::function<void(body_type&)> tonat = [](body_type& inp){
		inp = static_cast<int>(std::get<bool>(inp));
	};
	prims.emplace_back("tonat", 1, BOOL_INT, NAT_INT, tonat);


	// ここでtupleを引数に取って演算を定義していく
	std::function<void(std::vector<std::reference_wrapper<body_type>>)> add = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<int>(inp.at(0).get()) += std::get<int>(inp.at(1).get());
	};
	prims.emplace_back("add", 1, TUPLE_INT, NAT_INT, add, std::vector<int>({NAT_INT, NAT_INT}));

	std::function<void(std::vector<std::reference_wrapper<body_type>>)> sub = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<int>(inp.at(0).get()) -= std::get<int>(inp.at(1).get());
	};
	prims.emplace_back("sub", 1, TUPLE_INT, NAT_INT, sub, std::vector<int>({NAT_INT, NAT_INT}));

	std::function<void(std::vector<std::reference_wrapper<body_type>>)> mul = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<int>(inp.at(0).get()) *= std::get<int>(inp.at(1).get());
	};
	prims.emplace_back("mul", 1, TUPLE_INT, NAT_INT, mul, std::vector<int>({NAT_INT, NAT_INT}));

	std::function<void(std::vector<std::reference_wrapper<body_type>>)> div = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<int>(inp.at(0).get()) /= std::get<int>(inp.at(1).get());
	};
	prims.emplace_back("div", 1, TUPLE_INT, NAT_INT, div, std::vector<int>({NAT_INT, NAT_INT}));

	std::function<void(std::vector<std::reference_wrapper<body_type>>)> mod = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<int>(inp.at(0).get()) %= std::get<int>(inp.at(1).get());
	};
	prims.emplace_back("mod", 1, TUPLE_INT, NAT_INT, mod, std::vector<int>({NAT_INT, NAT_INT}));


	std::function<void(std::vector<std::reference_wrapper<body_type>>)> ifbool = [](std::vector<std::reference_wrapper<body_type>> inp){
		std::get<bool>(inp.at(0).get()) = std::get<bool>(inp.at(0).get()) ? std::get<bool>(inp.at(1).get()) : std::get<bool>(inp.at(2).get());
	};
	prims.emplace_back("ifbool", 1, TUPLE_INT, BOOL_INT, ifbool, std::vector<int>({BOOL_INT, BOOL_INT, BOOL_INT}));

	std::function<void(std::vector<std::reference_wrapper<body_type>>)> ifnat = [](std::vector<std::reference_wrapper<body_type>> inp){
		inp.at(0).get() = std::get<bool>(inp.at(0).get()) ? std::get<int>(inp.at(1).get()) : std::get<int>(inp.at(2).get());
	};
	prims.emplace_back("ifnat", 1, TUPLE_INT, NAT_INT, ifnat, std::vector<int>({BOOL_INT, NAT_INT, NAT_INT}));

}

auto match_func = [](std::string& inp, int st, int en){
	std::string subst = inp.substr(st, en - st);

	for(int index = 0; index < prims.size(); ++index){
		if(subst == prims.at(index).name)
			return index;
	}

	return MAX;

};

class Node{

public:
	Node(std::string& inp, int inp_st = 0, int inp_en = -1, int inp_type = -1) : 
		parent_str(inp)
	{
		// [st,en)の半開区間を持つ
		

		// 親ノードの働きをする
		if(inp_en == -1){
			st = 0;
			en = 0;
			type = PARENT;
			child.emplace_back(std::make_shared<Node>(inp, inp_st, parent_str.length()));

			return ;
		}

		st = inp_st;
		en = inp_en;

#ifdef DO_OUTPUT
		std::cout << "node : [" << st << " , " << en << ") -> \"";
		for(int index = st; index < en; ++index)
			std::cout << parent_str.at(index);
		std::cout << "\"" << std::endl;
#endif

		int fn_index = match_func(parent_str, st, en);
		if(fn_index != MAX){
			type = FUNC;
			value_type = prims.at(fn_index).ret_type;
			return ;
		}

		int ch_type = check_type(parent_str, st, en);

		if(ch_type != MAX){
			// 明示的に指定されているなら(targetかtypeなら)
			if(inp_type != -1)
				type = inp_type;
			else{
				type = VALUE;
				value_type = ch_type;
			}
		}

		else
			expand();
	}

	Node(std::string& inp, int inp_st, int inp_en, std::shared_ptr<Node> child_1, std::shared_ptr<Node> child_2) : 
		parent_str(inp)
	{
		if(inp_en == -1)
			inp_en = parent_str.length();


		st = inp_st;
		en = inp_en;

#ifdef DO_OUTPUT
		std::cout << "node : [" << st << " , " << en << ") -> \"";
		for(int index = st; index < en; ++index)
			std::cout << parent_str.at(index);
		std::cout << "\"" << std::endl;
#endif

		// 必ず関数適用になる
		type = APPLY;

		// ここで子の展開処理がされる
		child.push_back(child_1);
		child.push_back(child_2);

		// 親の展開処理はしない
	}

#ifdef DO_OUTPUT
	void output(int indent = 0){

		std::string indent_str(indent, ' ');
		std::string out_indent_str(indent + OUT_INDENT, ' ');

		std::string result;

		of << indent_str << "{" << std::endl;

		auto add_text = [&result, &out_indent_str](std::string head, std::string body, bool is_str = true, bool use_comma = true){
			result += out_indent_str + "\"" +  head + "\": " + (is_str ? "\"" : "")  + body + (is_str ? "\"" : "") + (use_comma ? "," : "") + "\n";
		};

		std::string type_str = type_to_str(type);

		std::string value_type_str = type_value_to_str(value_type);

		add_text("body", parent_str.substr(st, en - st));
		add_text("type", type_str);
		if(value_type != MAX)
			add_text("value_type", value_type_str);
		if(access_index != MAX)
			add_text("access_index", std::to_string(access_index));
		add_text("st", std::to_string(st), false);
		add_text("en", std::to_string(en), false, child.size());

		of << result;

		if(!child.empty())
			of << out_indent_str << "\"child\": [" << std::endl;

		for(auto it = child.begin(); it != child.end(); ++it){
			(*it)->output(indent + OUT_INDENT * 2);
			if(it != prev(child.end()))
				of << ",";
			of << std::endl;
		}

		if(!child.empty())
			of << out_indent_str << "]" << std::endl;

		of << indent_str + "}";

	}
#endif

	std::string str(){
		return parent_str.substr(st, en - st);
	}
	
	std::string strout(){
		if(type == PARENT)
			return child.at(0)->strout();

		else if(type == APPLY){
			return  child.at(0)->strout() + " " + child.at(1)->strout();
		}
		else if(type == ABST){
			return "@" + child.at(0)->strout() +  ":" + child.at(1)->strout() +  "." + child.at(2)->strout();
		}
		else
			return str();
	}

	std::vector<std::shared_ptr<Node>> child;

	std::string& parent_str;
	int st, en;

	int type;

	int value_type = MAX;
	int access_index = MAX;

	// 型検査とラベルつけ
	int check(){

		// apply時にabstの引数として渡される型とvariable_body->typeの型が一致しているか確かめる

		if(type == ABST){
			value_type = match_type(parent_str, child.at(1)->st, child.at(1)->en);
			child.at(2)->setType(child.at(0)->str(), value_type);
			for(auto ch : child)
				ch->check();
			return value_type;
		}

		if(type == APPLY){

			if(child.at(0)->type == FUNC){
				Primitive& prim = prims.at(match_func(parent_str, child.at(0)->st, child.at(0)->en));

				// funcの引数が合っているかどうかの型検査

				int check_1 = child.at(1)->check();
				if(prim.arg_type != check_1)
					typeCheckError(prim.arg_type, check_1);

				if(check_1 == TUPLE_INT){
					if(prim.tuple_types.size() != child.at(1)->child.size()){
						std::cerr << "error : tuple size is incorrect" << std::endl;
						typeCheckError(TUPLE_INT, TUPLE_INT);
					}
					for(int index = 0; index < prim.tuple_types.size(); ++index){
						if(prim.tuple_types.at(index) != child.at(1)->child.at(index)->check())
							typeCheckError(prim.tuple_types.at(index), child.at(1)->child.at(index)->type);
					}
				}

				return value_type = prim.ret_type;
			}

			else if(child.at(0)->type == ACCESS){

				if(child.at(1)->type != TUPLE){
					std::cerr << "operator access at not tuple function" << std::endl;
					abort();
				}

				int access = child.at(0)->access_index;
				if(access >= child.at(1)->child.size()){
					std::cerr << "out of range at access operator" << std::endl;
					abort();
				}
				value_type = child.at(1)->child.at(access)->check();
				return value_type;
			}

			int check_0 = child.at(0)->check();
			int check_1 = child.at(1)->check();
			if(check_0 != check_1)
				typeCheckError(check_0, check_1);
			return value_type = check_0;
		}
		// if(type == VALUE || type == FUNC)
		if(type == VALUE)
			return value_type;

		if(type == TUPLE)
			return TUPLE_INT;

		if(type == PARENT)
			for(auto ch : child)
				ch->check();
		return 0;
	}

	void setType(std::string target, int val){
		if(type == VALUE && str() == target && value_type == VARIABLE_INT)
			value_type = val;
		for(auto ch : child)
			ch->setType(target, val);
	}

	bool simplify(){

		bool flag = false;

		for(int index = 0; index < child.size(); ++index){ // 適用 -> 抽象の適用
			if(child.at(index)->type == APPLY && child.at(index)->child.at(0)->type == ABST){
				// index->0->1でtype
				child.at(index)->child.at(0)->child.at(2)->simplification(child.at(index)->child.at(0), child.at(index)->child.at(1));
				child.at(index) = child.at(index)->child.at(0)->child.at(2);

				flag = true;
			}
		}

		for(auto ch : child)
			flag |= ch->simplify();

		return flag;
	}

	// target.child[1]型のtarget.child[0]をexpr.str()で置き換える
	void simplification(std::shared_ptr<Node> target, std::shared_ptr<Node> expr){

		if(type == VALUE && target->child.at(0)->str() == str()){

			st = expr->st;
			en = expr->en;

			child.clear();
			if(check_type(parent_str, st, en) != MAX){
				type = VALUE;
				value_type = match_type(parent_str, target->child.at(1)->st, target->child.at(1)->en);
			}
			else
				expand();
		}
		else
			for(auto ch : child)
				ch->simplification(target, expr);
	}

	// 展開
	void expand(){

		// 関数宣言は必ず先頭にくる
		if(parent_str.at(st) == LT){

			// lambda抽象: @x:N.(x y)
			// let束縛   : $x(y)
			// 束縛はそれが出てきた(それ以降の)ネストをxに置き換える
			// [x->s]f = (@x.f) s
			// [x->y]f = $x(y) f
			// ここの空白は許されないって事にしておきます
			int open_index = match(parent_str, st, en, OPEN);

			int nest = 0;

			for(int index = open_index; index < en; ++index){
				if(parent_str.at(index) == OPEN)
					++nest;
				if(parent_str.at(index) == CLOSE){
					--nest;
					if(!nest){
						// 関数宣言の末尾
						type = LET;
						int pass_space = index;

						while(parent_str.at(pass_space + 1) == SPACE)
							++pass_space;

						child.emplace_back(std::make_shared<Node>(parent_str, st + 1, open_index));
						child.emplace_back(std::make_shared<Node>(parent_str, open_index + 1, index));

						child.emplace_back(std::make_shared<Node>(parent_str, pass_space + 1, en));
						return ;
					}
				}
			}
			parseError("let expr is incorrect");
		}

		if(parent_str.at(st) == LAMBDA){
			int colon_index = match(parent_str, st, en, COLON);
			if(en - 1 <= colon_index || colon_index < st + 2)
				parseError("colon is not found or out of range");

			child.push_back(std::make_shared<Node>(parent_str, st + 1, colon_index, TARGET));

			// ":"と"."の後にある空白は許容

			while(parent_str.at(colon_index + 1) == SPACE)
				++colon_index;

			int dot_index = match(parent_str, colon_index, en, DOT);
			child.push_back(std::make_shared<Node>(parent_str, colon_index + 1, dot_index, TYPE));

			while(parent_str.at(dot_index + 1) == SPACE)
				++dot_index;
			if(en - 1 <= dot_index || dot_index < colon_index + 2)
				parseError("dot is not found or out of range");

			child.push_back(std::make_shared<Node>(parent_str, dot_index + 1, en));

			type = ABST;
			return ;
		}
		else if(parent_str.at(st) == OPEN){
			int nest = 0;
			for(int index = st; index < en - 1; ++index){
				if(parent_str.at(index) == OPEN)
					++nest;
				if(parent_str.at(index) == CLOSE){
					--nest;
					if(!nest)nest = -MAX;
				}
			}

			int close_index = match(parent_str, st, en, CLOSE, false);
			if(nest == 1 && close_index == en - 1){

				++st;
				--en;

				// ここにtupleとして組ませる処理を書く
				int comma_index = st - 1;
				int split = st;
				int next_comma;
				while((next_comma = match_nest(parent_str, comma_index + 1, en, COMMA)) != MAX){

					if(comma_index + 1 == next_comma)
						parseError("comma postion is incorrect");

					comma_index = next_comma;

					// 空白の許容
					while(parent_str.at(comma_index + 1) == SPACE)
						++comma_index;

					type = TUPLE;
					value_type = TUPLE_INT;

					child.push_back(std::make_shared<Node>(parent_str, split, next_comma));
					split = comma_index + 1;
				}
				if(!child.empty()){
					child.push_back(std::make_shared<Node>(parent_str, comma_index + 1, en));
					return ;
				}


				// 括弧を除去して再度展開
				expand();
				return ;
			}
		}
		// "$" + natの形式であれば
		else if(parent_str.at(st) == AT && is_nat(parent_str, st + 1, en)){
			type = ACCESS;
			value_type = MAX;
			access_index = std::stoi(parent_str.substr(st + 1, en - (st + 1)));
			return ;
		}


		// 変数(variable)であれば(is_val:typeの形なら)
		int colon_index = match(parent_str, st, en, COLON);
		if(!(colon_index == st || colon_index > en - 2) && is_val(parent_str, st, colon_index) && is_val(parent_str, colon_index + 1, en)){
			type = VALUE;
			value_type = match_type(parent_str, colon_index + 1, en);
			en = colon_index;
			if(value_type == MAX)
				parseError("value type is incorrect");
			return ;
		}

		auto check_child = [&](int pos){
			if(child.size() != 3)
				return ;

			std::shared_ptr<Node> union_child = std::make_shared<Node>(parent_str, st, pos, child.at(0), child.at(1));

			std::shared_ptr<Node> new_child = child.at(2);
			child.clear();
			child.emplace_back(union_child);
			child.emplace_back(new_child);
		};

		std::function<void(int)> split_by_space = [&](int func_st){

			int space_index = match_nest(parent_str, func_st, en, SPACE);

			if(!space_index)
				parseError("space postion is incorrect");

			// not found
			else if(space_index == MAX){
				if(func_st == st)
					parseError("expr cannot split");
				child.push_back(std::make_shared<Node>(parent_str, func_st, en));
				check_child(func_st - 1);
			}

			else{
				// SPACEを区切りに分割
				child.push_back(std::make_shared<Node>(parent_str, func_st, space_index));
				check_child(func_st - 1);
				split_by_space(space_index + 1);
			}
		};

		type = APPLY;

		split_by_space(st);

		if(child.size() != 2)
			parseError("substring is not val and not found");

	}

	void parseError(std::string input_string = ""){
		std::cerr << "parseError : " << input_string << std::endl << "\"" << parent_str <<"\" at [" << st << "," << en << ")  -> ";
		for(int index = st; index < en; ++index)
			std::cerr << parent_str.at(index);
		std::cerr << std::endl;
		abort();
	}

	void typeCheckError(int inp_1, int inp_2){
		std::cerr << "typeCheckError : " << type_value_to_str(inp_1) << " != " << type_value_to_str(inp_2) << std::endl << "\"" << parent_str <<"\" at [" << st << "," << en << ")  -> ";
		for(int index = st; index < en; ++index)
			std::cerr << parent_str.at(index);
		std::cerr << std::endl;
		abort();
	}

};

class EvalNode{
public:
	body_type body;
	int type, value_type, access_index;
	int func_type = MAX;
	std::vector<std::shared_ptr<EvalNode>> child;

	EvalNode(std::shared_ptr<Node> node){
		type = node->type;
		value_type = node->value_type;
		access_index = node->access_index;

		// 評価の終わったnodeなら
		if(type == VALUE){
			if(value_type == NAT_INT){
				try{
					body = std::stoi(node->str());
				}
				catch (std::invalid_argument& e) {
					std::cerr << "EvalNode constructor error : " << "stoi: invalid argument -> " << node->str() << std::endl;
					abort();
				}
			}
			else if(value_type == BOOL_INT)
				body = (node->str() == "true");
		}
		else if(type == FUNC){
			func_type = match_func(node->parent_str, node->st, node->en);
			if(func_type == MAX){
				std::cerr << "func not match\n";
				abort();
			}
		}

		for(auto ch : node->child)
			child.emplace_back(std::make_shared<EvalNode>(ch));
	}

	bool eval(){
		// FUNCの適用が可能ならば
		bool flag = false;

		for(auto ch : child)
			flag |= ch->eval();

		for(int index = 0; index < child.size(); ++index){

			if(child.at(index)->type == APPLY && child.at(index)->child.at(0)->type == FUNC){
				if(child.at(index)->child.at(1)->type == VALUE){

					// ここで処理を行っている
					
					std::get<0>(prims.at(child.at(index)->child.at(0)->func_type).func)(child.at(index)->child.at(1)->body);

					child.at(index)->child.at(1)->value_type = prims.at(child.at(index)->child.at(0)->func_type).ret_type;
					child.at(index) = child.at(index)->child.at(1);

					flag = true;
				}
				else if(child.at(index)->child.at(1)->type == TUPLE){

					child.at(index)->child.at(1)->eval();

					std::vector<std::reference_wrapper<body_type>> vec_ref;
					for(auto& ch : child.at(index)->child.at(1)->child)
						vec_ref.emplace_back(ch->body);
					std::get<1>(prims.at(child.at(index)->child.at(0)->func_type).func)(vec_ref);

					child.at(index)->child.at(1)->child.at(0)->value_type = prims.at(child.at(index)->child.at(0)->func_type).ret_type;
					child.at(index) = child.at(index)->child.at(1)->child.at(0);
				}
			}
			else if(child.at(index)->type == APPLY && child.at(index)->child.at(0)->type == VALUE && child.at(index)->child.at(1)->type == VALUE){

				auto& body_0 = child.at(index)->child.at(0)->body;
				auto& body_1 = child.at(index)->child.at(1)->body;
				
				int body_index = body_0.index();
				if(body_index != body_1.index())
					break;
				
				// int
				if(body_index == 0){
					std::get<0>(body_0) += std::get<0>(body_1);
				}
				// bool
				else if(body_index == 1){
					std::get<1>(body_0) &= std::get<1>(body_1);
				}

				child.at(index) = child.at(index)->child.at(0);

				flag = true;
			}
			else if(child.at(index)->type == APPLY && child.at(index)->child.at(0)->type == ACCESS && child.at(index)->child.at(1)->type == TUPLE){

				child.at(index) = child.at(index)->child.at(1)->child.at(child.at(index)->child.at(0)->access_index);
				flag = true;
			}
		}

		return flag;
	}

	void out(int indent = 0){
		std::string indent_str(indent, ' ');
		std::string out_indent_str(indent + OUT_INDENT, ' ');
		std::cout << indent_str + "{\n";

		std::cout << out_indent_str + "\"type\" :  " + type_value_to_str(value_type) << std::endl;
		
		std::visit([&out_indent_str](auto val){std::cout << out_indent_str << "\"value\" : " << val << std::endl;}, body);

		
		for(auto ch : child)
			ch->out(indent + OUT_INDENT * 2);
		std::cout << indent_str + "}\n";

	}

	void strout(){
		if(type == PARENT){
			child.at(0)->strout();
			std::cout << std::endl;
		}

		else if(type == APPLY){
			child.at(0)->strout();
			std::cout << " ";
			child.at(1)->strout();
		}
		else if(type == ABST){
			std::cout << "@";
			child.at(0)->strout();
			std::cout << ":";
			child.at(1)->strout();
			std::cout << ".";
			child.at(2)->strout();
		}
		else if(type == TUPLE){
			std::cout << "(";
			for(auto it = child.begin(); it != child.end(); ++it){
				if(it != child.begin())
					std::cout << ",";
				(*it)->strout();
			}
			std::cout << ")";
		}
		else{
			std::visit([](auto val){std::cout << val;}, body);
#ifdef DO_OUTPUT
			std::cout << ":\"" << type_value_to_str(value_type) << "\"";
#endif
		}
	}

	bool finished(){
		if(type != VALUE && type != PARENT)
			return false;

		for(auto ch : child)
			if(!ch->finished())
				return false;

		return true;
	}

};

void evalAll(std::shared_ptr<Node> node, std::shared_ptr<EvalNode> ev_ptr){

	while(node->simplify());

	// json形式でのファイル出力
#ifdef DO_OUTPUT
	node->output();
#endif

	ev_ptr = std::make_shared<EvalNode>(node);

	while(ev_ptr->eval());

#ifdef DO_OUTPUT
	ev_ptr->child.at(0)->out();
	std::cout << std::endl;

#endif
	ev_ptr->strout();

#ifdef DO_OUTPUT
	std::cout << (ev_ptr->finished() ? "successfully finished\n" : "failed\n");
#endif
}

int main(){

	std::string input;

#ifdef USE_CIN
	

	input = "add (div (!b, !a), tonat (any (mod (!b, !a))))";

	auto replace = [&input](std::string before, std::string after){

		auto pos = input.find(before);

		while(pos != std::string::npos){
			input.replace(pos, before.size(), after);
			pos = input.find(before, pos + after.size());
		}
	};

	std::string a, b;
	std::cin >> a >> b;

	replace("!a", a);
	replace("!b", b);

#else

	// 標準入力をそのまま投げる

	std::string cinp;
	while(std::getline(std::cin, cinp))
		input += cinp;

#endif

	init();
	
	// 読み込んだ文字列を構文解析
	std::shared_ptr<Node> par = std::make_shared<Node>(input);

	// 型検査
	par->check();

	std::shared_ptr<EvalNode> ev_ptr;

	// 簡約と評価
	evalAll(par, ev_ptr);

#ifdef DO_OUTPUT
	of << std::endl;
	of.close();
#endif

}