ACM-ICPC 2016 Asia Tsukuba Regional, E 解法

E: Infallibly Crack Perplexing Cryptarithm

問題

虫食い等式が与えられる。数式は2進数で数を表記し、BNFは次のように与えられる。

Q ::= E'='E
E ::= T | E'+'T | E'-'T
T ::= F | T'*'F
F ::= N | '-'F | '('E')'
N ::= '0' | '1'B
B ::= empty | '0'B | '1'B

演算子の優先順位はBNFと同じ。
虫食いは大文字小文字を区別するアルファベット全て。同じアルファベットは同じ記号に、異なるアルファベットは異なる記号に割り当てなければならない。ただし、虫喰いされていない記号をアルファベットに割り当ててもよい。
正しい等式は何通りあるか答えよ。
長さは31以下。

解法

割当のルールのため8の階乗通りの式を試せばよい。
パーサは2進数である以外は一般的なものだが文法が壊れたものを読む必要があるのでそれだけ注意する。
BNFを直接写す前にEやTのルールを

E ::= T (('+'|'-')T)*
T ::= F ('*'F)*

に変換する。

コード

パーサはspaghetti source先生 Spaghetti Source - 再帰下降型構文解析 ( LL(1) )を参考に。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

struct Result {
    char *p;
    int val;
    Result() : p(NULL), val(0) {}
};

struct Parser {
    Result Q(char *p) {
	Result r = E(p);
	if (r.p == 0) return r;
	Result ret;

	if (*(r.p) == '=') {
	    Result r2 = E(r.p+1);
	    if (r2.p == 0) return ret;

	    if (*(r2.p) == 0) {
		ret.val = (r.val == r2.val);
	    }
	}
	return ret;
    }

    Result E(char *p) {
	Result r = T(p);
	if (r.p == 0) return r;

	while (*(r.p) == '+' || *(r.p) == '-') {
	    Result r2 = T(r.p+1);
	    if (r2.p == 0) return r2;

	    if (*(r.p) == '+') {
		r.val += r2.val;
	    } else {
		r.val -= r2.val;
	    }
	    r.p = r2.p;
	}

	return r;
    }

    Result T(char *p) {
	Result r = F(p);
	if (r.p == 0) return r;

	while (*(r.p) == '*') {
	    Result r2 = F(r.p+1);
	    if (r2.p == 0) return r2;

	    r.val *= r2.val;
	    r.p = r2.p;
	}

	return r;
    }

    Result F(char *p) {
	if (*p == '-') {
	    Result r = F(p+1);
	    r.val *= -1;
	    return r;
	}
	if (*p == '(') {
	    Result r = E(p+1);
	    if (r.p == 0 || *(r.p) != ')') return Result();
	    r.p++;
	    return r;
	}
	return N(p);
    }

    Result N(char *p) {
	Result r;
	if (*p != '0' && *p != '1') return r;

	if (*p == '0' && (*(p+1) == '0' || *(p+1) == '1')) return r;

	while (isdigit(*p)) {
	    r.val = r.val * 2 + (*p - '0');
	    p++;
	}
	r.p = p;
	return r;
    }
};


const char *OP = "=01+-*()";
char env[256];
char S[99];
int N;

int ans = 0;

void dfs(int I) {
    if (I == N) {
	ans += Parser().Q(S).val;
    } else {
	if (isalpha(S[I])) {
	    char S_bak = S[I];
	    char env_bak = env[S[I]];

	    if (env_bak == 0) {
		REP (j, 8) {
		    if (env[OP[j]] == 0) {
			env[OP[j]] = S_bak;
			env[S_bak] = OP[j];
			S[I] = OP[j];
			dfs(I+1);
			env[OP[j]] = env[S_bak] = 0;
			S[I] = S_bak;
		    }
		}
	    } else {
		S[I] = env_bak;
		dfs(I+1);
		S[I] = S_bak;
	    }
	} else {
	    dfs(I+1);
	}
    }
}

int main() {
    scanf("%s", S);
    N = strlen(S);

    dfs(0);

    printf("%d\n", ans);

    return 0;
}

感想

大変頻出な構文解析問題。コードは長いがやることはBNF写すだけなのでタイピングゲーム。
Leading zerosの判定忘れて詰まってしまった。