[表达式]七个古墓

题目描述

塔•拉夏被埋葬在术士峡谷的七个古墓中的一个。

塔•拉夏的古墓一共有七种不同的符号，分别用 $A,B,C,D,E,F,G$ 表示。每个古墓中分别封印着一种力量，用 $1,2,3,4,5,6,7$ 表示。为了防止以后有人取得这些力量，赫拉迪姆将这些对应的关系全部隐藏起来了。

为了获得这七种力量，你终于找到了一点线索：一个古代赫拉迪姆留下的式子。这个式子表示了七种力量对应的关系。经过破译，终于知道将七种符号所表示的力量的代号分别代进式子中，使得等式成立的，就是开启封印的钥匙。

写一个程序解开这个迷题。

输入格式

一行一个字符串，为一个只有变量 $A,B,C,D,E,F,G$ 的等式。式子中只含有字母、加、减、乘号以及括号和一个等号，比如 ABC 表示 $100\times A+10\times B+C$，字符串长度不超过 $200$。

输出格式

一行，输出对应等式的解。如果有多种可能，输出 $ABCDEFG$ 表示十进制数最小的一个。输入数据保证有解。

样例

样例输入1：

(A+B)*C-E*(C+D)=FF

样例输出1：

(2+6)*7-1*(7+5)=44

数据范围

字符串长度不超过 $200$。

题解

先依次枚举 $A,B,C,D,E,F,G$ 的值，在等号左右两边进行计算，如果相等，就是答案，输出 $ABCDEFG$ 最小的一个即可。

枚举 $A,B,C,D,E,F,G$ 的值：

int fl[120], p[120];
int tmp;//记录等号的位置
void ff(int x){
	if(x > 7){
		long long ans = dfs(0, tmp - 1);//计算左边的值
		long long pp = dfs(tmp + 1, l - 1);//计算右边的值
		if(ans == -1 && pp == -1){//不存在
			putchar('=');
			exit(0); 
		}
		if(ans == pp){//相等
			fll = 1;
			dfs(0, tmp - 1);//递归输出左边的表达式
			putchar('=');
			dfs(tmp + 1, l - 1); //递归输出右边的表达式
			exit(0);
		}
	}
	for(int i = 1; i <= 7; ++ i){//从小到大枚举值为 x 的字母
		if(fl[i]){//已经枚举过
			continue;
		}
		//标记
		p['A' + x - 1] = i;
		fl[i] = 1;
		ff(x + 1);
		//回溯
		fl[i] = 0;
	}
}

计算表达式的值：

int p[120], fl[120];
int d(char x){
	return p[x];
}
long long isnum(int x, int y){//判断是否完全为字符
	long long p = 0;//记录字符对应的答案
	for(int i = x; i <= y; ++ i){
		if(s[i] >= 'A' && s[i] <= 'G'){
			p = p * 10 + d(s[i]);
		}
		else{
			return -1;//不是
		}
	}
	return p;
}
int follow(int x, int y){//寻找下一个匹配的括号
	int t = 0;//记录层数
	for(int i = x; i <= y; ++ i){
		if(s[i] == '('){
			++ t;
		}
		else if(s[i] == ')'){
			-- t;
		}
		if(t == 0){
			return i;//匹配的右括号
		}
	}
	return -1;
}
int f_find(int x, int y){//找优先级最低的
	int k = -1, t = 0;
	for(int i = y; i >= x; -- i){//从右往左
		if(s[i] == '('){
			++ t;
		}
		if(s[i] == ')'){
			-- t;
		}
		if(t == 0 && (s[i] == '+' || s[i] == '-')){//在括号外的加减号，直接计算
			return i;
		}
		if(t == 0 && (s[i] == '*' || s[i] == '/') && (k == -1)){
			k = i;//记录最先的乘除号
		}
	}
	return k;
}
long long js(long long x, long long y, char z){//计算
	if(z == '+'){
		return x + y;
	}
	if(z == '-'){
		return x - y;
	}
	if(z == '*'){
		return x * y;
	}
	return x / y;
}
bool fll = 0;//是否输出表达式
long long dfs(int l, int r){
	if(l > r){//不存在
		return -1;
	}
	long long t = isnum(l, r);
	if(t != -1){//为变量
		if(fll){
			printf("%lld", t);
		}
		return t;
	}
	if(s[l] == '(' && (follow(l, r) == r)){//左右都是括号
		if(fll){
			printf("(");
		}
		long long tt = dfs(l + 1, r - 1);
		if(fll){
			printf(")");
		}
		return tt;
	}
	int u = f_find(l, r);//优先级最低的位置
	long long t1 = dfs(l, u - 1);//左边
	if(fll){
		printf("%c", s[u]);
	}
	long long t2 = dfs(u + 1, r);//右边
	return js(t1, t2, s[u]);//计算
}