CodeIQ 「中学入試から：単位のある計算」 解答コード

_sugaku_tani_keisan.cpp

#include <cstdio>
#include <vector>
#include <string>
#include <cctype>

/*

### 入力される方程式として仮定するBNF

	<方程式> = <式> "=" <式>
	<式>     = <項> | <項> <演算子> <式>
	<演算子> = "" | "+" | "-"
	<項>     = <数値> <単位>
	<数値>   = "□" | <数字列>
	<数字列> = <数字> | <数字> <数字列>
	<数字>   = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
	<単位>   = "km" | "cm" | "mm" | "m" | "kg" | "mg" | "g" | "日" | "時間" | "分" | "秒"

### 式の解釈

	* 方程式全体の和が0になってくれたら嬉しい
	* 最初は加算、""以外の演算子があったら次の項からその演算子に従って加減算を行う
	* "="があったら減算モードにし、それ以降の演算子の意味を反転する
	* 単位は直前の数値に掛ける値として解釈する。次元？いえ、知らない子ですね。
	* 1個の方程式に"□"はちょうど1個しか入っていないと仮定

*/

typedef long long integer;

// 整数を文字列に変換する
std::string integer2str(integer n) {
	if (n < 0) return std::string("-") + integer2str(-n);
	if (n == 0) return std::string("0");

	char ret[] = {(char)((int)(n % 10) + '0'), '\0'};
	if (n < 10) {
		return std::string(ret);
	} else {
		return integer2str(n / 10) + std::string(ret);
	}
}

struct unit_info_data {
	std::string unit;
	integer multi;

	unit_info_data(){}
	unit_info_data(const std::string& unit_, integer multi_ = 0):unit(unit_), multi(multi_){}
};

// 分子と分母を受け取り、約分したデータを保持する。等しいかの比較ができる。
class fraction_t {
	private:
		integer numerator; // 分子
		integer denominator; // 分母

		static integer gcd(integer a, integer b) {
			if (a < 0) a = -a;
			if (b < 0) b = -b;
			while (b > 0) {
				integer r = a % b;
				a = b;
				b = r;
			}
			return a;
		}
	public:
		fraction_t():numerator(0),denominator(1){}
		fraction_t(integer num):numerator(num),denominator(1){}
		fraction_t(integer bunsi, integer bunbo) {
			integer g = gcd(bunsi, bunbo);
			numerator = bunsi / g;
			denominator = bunbo / g;
			if (denominator < 0) {
				numerator = -numerator;
				denominator = -denominator;
			}
		}
		bool operator==(const fraction_t& f) const {
			return numerator == f.numerator && denominator == f.denominator;
		}
		bool operator!=(const fraction_t& f) const {
			return !(*this == f);
		}
		std::string to_string() const {
			if (denominator == 1) {
				return integer2str(numerator);
			} else {
				return integer2str(numerator) + std::string("/") + integer2str(denominator);
			}
		}
};

// 直前の方程式の要素の種類を示す
enum expr_status {
	EXPR_BEGIN,
	EXPR_NUMBER,
	EXPR_SQUARE,
	EXPR_OPERATOR,
	EXPR_UNIT
};

// 方程式を1本解く
fraction_t solve_one_equation(const std::string& equation) {
	static const std::string square = "□";
	static std::vector<unit_info_data> unit_info;
	if (unit_info.empty()) {
		// 初回なので、単位リストを初期化する
		unit_info.push_back(unit_info_data("kg", 1000*1000));
		unit_info.push_back(unit_info_data("mg",         1));
		unit_info.push_back(unit_info_data( "g",      1000));

		unit_info.push_back(unit_info_data("km", 1000*1000));
		unit_info.push_back(unit_info_data("cm",        10));
		unit_info.push_back(unit_info_data("mm",         1));
		unit_info.push_back(unit_info_data( "m",      1000)); // 順番によって誤動作するので注意

		unit_info.push_back(unit_info_data(  "日", 24*60*60));
		unit_info.push_back(unit_info_data("時間",    60*60));
		unit_info.push_back(unit_info_data(  "分",       60));
		unit_info.push_back(unit_info_data(  "秒",        1));
	}

	integer equation_sum = 0; // 方程式の項の和
	integer current_number = 0; // 今の数値
	integer square_multi = 0; // 四角の係数(単位)
	bool current_number_is_square = false; // 今の数値が四角かのフラグ
	bool square_is_plus = true; // 四角を加算するかのフラグ
	bool current_mode_is_plus = true; // 今加算モードかのフラグ
	bool invert_operator = false; // 演算子の意味を反転させるかのフラグ
	expr_status stat = EXPR_BEGIN; // 直前の式の要素(エラーチェック用)

	// 式のパースを実行する
	for (unsigned int i = 0; i < equation.size();) {
		if (isdigit(equation[i])) {
			// 数字
			if (stat == EXPR_SQUARE) {
				throw std::string("□ and numbers can't be mixed");
			}
			current_number = current_number * 10 + (equation[i] - '0');
			i++;
			stat = EXPR_NUMBER;
		} else if (equation.substr(i, square.size()) == square) {
			// 四角
			if (stat == EXPR_NUMBER) {
				throw std::string("□ and numbers can't be mixed");
			}
			current_number_is_square = true;
			i += square.size();
			stat = EXPR_SQUARE;
		} else if (equation[i] == '+' || equation[i] == '-') {
			// 演算子
			if (stat == EXPR_NUMBER || stat == EXPR_SQUARE) {
				throw std::string("unit is missing");
			}
			current_mode_is_plus = (equation[i] == '+');
			if(invert_operator) current_mode_is_plus = !current_mode_is_plus;
			i++;
			stat = EXPR_OPERATOR;
		} else if (equation[i] == '=') {
			// 等号
			if (stat == EXPR_NUMBER || stat == EXPR_SQUARE) {
				throw std::string("unit is missing");
			}
			if (stat == EXPR_OPERATOR) {
				throw std::string("stray operator before =");
			}
			if (stat == EXPR_BEGIN) {
				throw std::string("expression is missing before =");
			}
			invert_operator = !invert_operator;
			current_mode_is_plus = false;
			i++;
			stat = EXPR_BEGIN;
		} else {
			// 単位？
			if (stat != EXPR_NUMBER && stat != EXPR_SQUARE) {
				throw std::string("missing number(s) before unit");
			}
			bool unit_found = false;
			for (unsigned int j = 0; j < unit_info.size(); j++) {
				const std::string& unit = unit_info[j].unit;
				if (equation.substr(i, unit.size()) == unit) {
					// マッチする単位が見つかった
					if (current_number_is_square) {
						if(square_multi > 0) {
							// "□"が複数ある
							throw std::string("multiple □ detected");
						}
						square_is_plus = current_mode_is_plus;
						square_multi = unit_info[j].multi;
					} else {
						integer current_value = current_number * unit_info[j].multi;
						if (current_mode_is_plus) {
							equation_sum += current_value;
						} else {
							equation_sum -= current_value;
						}
					}
					current_number_is_square = false;
					current_number = 0;
					i += unit.size();
					unit_found = true;
					break;
				}
			}
			if(!unit_found) {
				throw std::string("unsupported unit");
			}
			stat = EXPR_UNIT;
		}
	}
	if (stat != EXPR_UNIT) {
		throw std::string("invalid equation");
	}

	// 方程式を解く
	if (square_multi <= 0) {
		throw std::string("no □ detected");
	}
	// この時点で解くべき方程式は equation_sum + □ * square_multi == 0
	// もしくは equation_sum - □ * square_multi == 0
	if (square_is_plus) equation_sum = -equation_sum;
#if 0
	// 解が条件をみたすかチェック
	if (equation_sum % square_multi != 0) {
		char message[1024];
		sprintf(message, "the answer is not an integer(%s/%s)",
			integer2str(equation_sum).c_str(), integer2str(square_multi).c_str());
		throw std::string(message);
	}
	if (equation_sum <= 0) {
		char message[1024];
		sprintf(message, "the answer is not positive(%s)",
			integer2str(equation_sum / square_multi).c_str());
		throw std::string(message);
	}
#endif
	// 答えを返す
	return fraction_t(equation_sum, square_multi);
}

int main(void) {
	std::vector<std::string> answer_id_list;
	std::vector<std::string> error_id_list;
	for (;;) {
		char id_char[1024];
		char equation1_char[1024];
		char equation2_char[1024];
		std::string id, equation1, equation2;
		if (scanf("%s%s%s", id_char, equation1_char, equation2_char) != 3) break;
		id = id_char;
		equation1 = equation1_char;
		equation2 = equation2_char;
		fraction_t equation1_answer, equation2_answer;
		bool error_flag = false;
		try {
			equation1_answer = solve_one_equation(equation1);
		} catch (std::string e) {
			printf("ERROR on %s (1) : %s\n", id.c_str(), e.c_str());
			error_flag = true;
		}
		try {
			equation2_answer = solve_one_equation(equation2);
		} catch (std::string e) {
			printf("ERROR on %s (2) : %s\n", id.c_str(), e.c_str());
			error_flag = true;
		}
		if (!error_flag) {
			if(equation1_answer != equation2_answer) {
				printf("%s : different answer (%s vs %s)\n", id.c_str(),
					equation1_answer.to_string().c_str(), equation2_answer.to_string().c_str());
				answer_id_list.push_back(id);
			} else {
				printf("%s : same answer (%s)\n", id.c_str(), equation1_answer.to_string().c_str());
			}
		} else {
			error_id_list.push_back(id);
		}
	}
	if (!answer_id_list.empty()) {
		printf("\nID list of answers:\n%s", answer_id_list[0].c_str());
		for (unsigned int i = 1; i < answer_id_list.size(); i++) {
			printf(",%s", answer_id_list[i].c_str());
		}
		printf("\nFound %u answer(s).\n", (unsigned int)answer_id_list.size());
	} else {
		puts("\nFound no answers.");
	}
	if(!error_id_list.empty()) {
		printf("\nID list of errors:\n%s", error_id_list[0].c_str());
		for (unsigned int i = 1; i < error_id_list.size(); i++) {
			printf(",%s", error_id_list[i].c_str());
		}
		printf("\nFound %u error(s).\n", (unsigned int)error_id_list.size());
	} else {
		puts("\nFound no errors.");
	}
	return 0;
}

answer.txt

【解答】
111,112,222,223,333,334,444,445,555,556,666,667,777,778,888,889,999

【感想・工夫した点など】
とりあえず、単位を係数とみなして方程式を解く方針を立てた。
最初はPerlのevalを用いて計算し、二分探索かなんかで解を求めようかと思ったが、
やっぱりevalに頼らずに構文解析を行うことにした。

入力の方程式は、以下のBNFに従うと仮定した。
	<方程式> = <式> "=" <式>
	<式>     = <項> | <項> <演算子> <式>
	<演算子> = "" | "+" | "-"
	<項>     = <数値> <単位>
	<数値>   = "□" | <数字列>
	<数字列> = <数字> | <数字> <数字列>
	<数字>   = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
	<単位>   = "km" | "cm" | "mm" | "m" | "kg" | "mg" | "g" | "日" | "時間" | "分" | "秒"

また、入力の数値はすべて十進数であると仮定した。

最初は1個の□には正の整数が1個だけ入ると仮定していた(例えば"10"は数字2個だが、1個の整数とみなす)が、
この仮定では例えばT14の答えが0になってしまい、サンプルと矛盾してしまった。
そこで、今回の問題で□に入る数はすべて有理数であると考えられるので、
答えが0以上の数aの時は(1-1+a)、負の数-bの時は(1-1-b)と書くことで、
正の整数が入った形で任意の有理数を表現し、□に入れることができる。
「□には必ず正の整数が入ります。」とは書かれているが、正の整数以外は入らないとは書かれていないので、
この解釈で問題文、サンプルの両方に矛盾しない。

□に入る数が負の数や整数でない数になるケースはなさそうだったので、
自分で以下のテストケースを作成し、テストを行った。

S01	1m+□cm=90cm	10時間+□時間=0時間
S02	1m+□m=110cm	□分=6秒
S03 1m+□m=90cm	□時間=360秒-720秒

また、「長さ・重さ・時間 しかありません。」という条件があるのに、
g系の質量の単位が入っているのは不正な入力であるが、実装への大きな影響は無いので無視する。

【言語と処理系】
言語 : C++
処理系 : g++ (GCC) 4.8.1
コンパイルオプション : -O2 -Wall -Wextra -s -static

【ソースコード】
省略