表达式得到期望结果的组成种数

给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。
express=“1^0|0|1”，desired=false。
只有1^((0|0)|1)和1^(0|(0|1))的组合可以得到false。返回2。
express=“1”，desired=false。
没有组合可以得到false。返回0。

思路 & 代码

暴力递归

先对表达式必须进行判断，必须满足一下几点

  • 长度必须为偶数
  • 奇数位上是0或者1
  • 偶数位上是^|&

然后对于每一个运算符作为分界点，分别计算左右两边的方法数使得满足disired，然后相乘得到方法数，再把所有方法数相加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//判断字符串是否合法
public static boolean isValid(char[] exp) {
	//长度为偶数
	if ((exp.length & 1) == 0) {
		return false;
	}
	//奇数位是0或1
	for (int i = 0; i < exp.length; i = i + 2) {
		if ((exp[i] != '1') && (exp[i] != '0')) {
			return false;
		}
	}
	//偶数为是&,|,^
	for (int i = 1; i < exp.length; i = i + 2) {
		if ((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^')) {
			return false;
		}
	}
	return true;
}
public static int num1(String express, boolean desired) {
	if (express == null || express.equals("")) {
		return 0;
	}
	char[] exp = express.toCharArray();
	if (!isValid(exp)) {
		return 0;
	}
	return p(exp, desired, 0, exp.length - 1);
}
//判断l到r上的表达式有多少种满足desired的方法
public static int p(char[] exp, boolean desired, int l, int r) {
	if (l == r) {
		if (exp[l] == '1') {
			return desired ? 1 : 0;
		} else {
			return desired ? 0 : 1;
		}
	}
	int res = 0;
	if (desired) {
		//以位运算符分割表达式，分别计算表达的值
		//总的可能数为左边可能数乘以右边可能数
		for (int i = l + 1; i < r; i += 2) {
			//以该运算符为分界点
			switch (exp[i]) {
			case '&':
				//desired为1，运算符是&,左右必须都是true
				res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
				break;
			case '|':
				//desired为1，运算符是|,左1右0,左0右1，左1右1
				res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
				res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
				res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
				break;
			case '^':
				//desired为1，运算符是^,左1右0,左0右1
				res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
				res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
				break;
			}
		}
	} else {
		for (int i = l + 1; i < r; i += 2) {
			switch (exp[i]) {
			case '&':
				res += p(exp, false, l, i - 1) * p(exp, true, i + 1, r);
				res += p(exp, true, l, i - 1) * p(exp, false, i + 1, r);
				res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
				break;
			case '|':
				res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
				break;
			case '^':
				res += p(exp, true, l, i - 1) * p(exp, true, i + 1, r);
				res += p(exp, false, l, i - 1) * p(exp, false, i + 1, r);
				break;
			}
		}
	}
	return res;
}

优化递归

使用数组记录算过的值
由于p(char[] exp, boolean desired, int l, int r)递归中有3个变量，应该使用三维表进行记录
但是使用2张二维表就可以，因为boolean desired只有真假两种取值
仍然是以位运算符号作为分割，计算所有的方法数，并记录

  • t[i][j]表示第i到j([i,j])的exp中结果为true的结果数
  • f[i][j]表示第i到j([i,j])的exp中结果为false的结果数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    //优化递归，记录所计算的值
    //p(char[] exp, boolean desired, int l, int r)递归中有3个变量，但是使用2张二维表就可以
    //一个表记录结果是true，另一个记录结果是false
    public static int num2(String express, boolean desired) {
    	if (express == null || express.equals("")) {
    		return 0;
    	}
    	char[] exp = express.toCharArray();
    	if (!isValid(exp)) {
    		return 0;
    	}
    	//t[i][j]表示第i到j的exp中结果为true的结果数
    	int[][] t = new int[exp.length][exp.length];
    	//f[i][j]表示第i到j的exp中结果为false的结果数
    	int[][] f = new int[exp.length][exp.length];
    	t[0][0] = exp[0] == '0' ? 0 : 1;
    	f[0][0] = exp[0] == '1' ? 0 : 1;
    	//以i为尾，j为头，算t[i][j]与f[i][j]
    	//依次向两边扩散，计算
    	for (int i = 2; i < exp.length; i += 2) {
    		//t[i][i]表示第i个位置为true的结果数
    		//因此只要看是t[i][i]的值，值1返回1，值0返回0
    		t[i][i] = exp[i] == '0' ? 0 : 1;
    		f[i][i] = exp[i] == '1' ? 0 : 1;
    		for (int j = i - 2; j >= 0; j -= 2) {
    			//以k+1为分界，判断前面和后后的组成数目
    			for (int k = j; k < i; k += 2) {
    				
    				if (exp[k + 1] == '&') {
    					//k+1是&，结果是true的可能是前1后1
    					t[j][i] += t[j][k] * t[k + 2][i];
    					//k+1是&，结果是false的可能是前1后0，前0后1，前0后0
    					//这里做了合并，先算前1后0和前0后0的结果，再加上前0后1
    					f[j][i] += (f[j][k] + t[j][k]) * f[k + 2][i] + f[j][k] * t[k + 2][i];
    				} else if (exp[k + 1] == '|') {
    					t[j][i] += (f[j][k] + t[j][k]) * t[k + 2][i] + t[j][k] * f[k + 2][i];
    					f[j][i] += f[j][k] * f[k + 2][i];
    				} else {
    					t[j][i] += f[j][k] * t[k + 2][i] + t[j][k] * f[k + 2][i];
    					f[j][i] += f[j][k] * f[k + 2][i] + t[j][k] * t[k + 2][i];
    				}
    			}
    		}
    	}
    	return desired ? t[0][t.length - 1] : f[0][f.length - 1];
    }