| 167 | } |
| 168 | |
| 169 | public static int countR(String exp, boolean result, int start, int end) { |
| 170 | if (start == end) { |
| 171 | if (exp.charAt(start) == '1' && result) { |
| 172 | return 1; |
| 173 | } else if (exp.charAt(start) == '0' && !result) { |
| 174 | return 1; |
| 175 | } |
| 176 | return 0; |
| 177 | } |
| 178 | int c = 0; |
| 179 | if (result) { |
| 180 | for (int i = start + 1; i <= end; i += 2) { |
| 181 | char op = exp.charAt(i); |
| 182 | if (op == '&') { |
| 183 | c += countR(exp, true, start, i - 1) * countR(exp, true, i + 1, end); |
| 184 | } else if (op == '|') { |
| 185 | c += countR(exp, true, start, i - 1) * countR(exp, false, i + 1, end); |
| 186 | c += countR(exp, false, start, i - 1) * countR(exp, true, i + 1, end); |
| 187 | c += countR(exp, true, start, i - 1) * countR(exp, true, i + 1, end); |
| 188 | } else if (op == '^') { |
| 189 | c += countR(exp, true, start, i - 1) * countR(exp, false, i + 1, end); |
| 190 | c += countR(exp, false, start, i - 1) * countR(exp, true, i + 1, end); |
| 191 | } |
| 192 | } |
| 193 | } else { |
| 194 | for (int i = start + 1; i <= end; i += 2) { |
| 195 | char op = exp.charAt(i); |
| 196 | if (op == '&') { |
| 197 | c += countR(exp, false, start, i - 1) * countR(exp, true, i + 1, end); |
| 198 | c += countR(exp, true, start, i - 1) * countR(exp, false, i + 1, end); |
| 199 | c += countR(exp, false, start, i - 1) * countR(exp, false, i + 1, end); |
| 200 | } else if (op == '|') { |
| 201 | c += countR(exp, false, start, i - 1) * countR(exp, false, i + 1, end); |
| 202 | } else if (op == '^') { |
| 203 | c += countR(exp, true, start, i - 1) * countR(exp, true, i + 1, end); |
| 204 | c += countR(exp, false, start, i - 1) * countR(exp, false, i + 1, end); |
| 205 | } |
| 206 | } |
| 207 | } |
| 208 | return c; |
| 209 | } |
| 210 | |
| 211 | public static int countDP(String exp, boolean result, int start, int end, HashMap<String, Integer> cache) { |
| 212 | String key = "" + result + start + end; |