| 274 | } |
| 275 | |
| 276 | public static int countDPEff(String exp, boolean result, int start, int end, HashMap<String, Integer> cache) { |
| 277 | String key = "" + start + end; |
| 278 | int count = 0; |
| 279 | if (!cache.containsKey(key)) { |
| 280 | if (start == end) { |
| 281 | if (exp.charAt(start) == '1') { |
| 282 | count = 1; |
| 283 | } else { |
| 284 | count = 0; |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | for (int i = start + 1; i <= end; i += 2) { |
| 289 | char op = exp.charAt(i); |
| 290 | if (op == '&') { |
| 291 | count += countDPEff(exp, true, start, i - 1, cache) * countDPEff(exp, true, i + 1, end, cache); |
| 292 | } else if (op == '|') { |
| 293 | int left_ops = (i - 1 - start) / 2; // parens on left |
| 294 | int right_ops = (end - i - 1) / 2; // parens on right |
| 295 | int total_ways = total(left_ops) * total(right_ops); |
| 296 | int total_false = countDPEff(exp, false, start, i - 1, cache) * countDPEff(exp, false, i + 1, end, cache); |
| 297 | count += total_ways - total_false; |
| 298 | } else if (op == '^') { |
| 299 | count += countDPEff(exp, true, start, i - 1, cache) * countDPEff(exp, false, i + 1, end, cache); |
| 300 | count += countDPEff(exp, false, start, i - 1, cache) * countDPEff(exp, true, i + 1, end, cache); |
| 301 | } |
| 302 | } |
| 303 | cache.put(key, count); |
| 304 | } else { |
| 305 | count = cache.get(key); |
| 306 | } |
| 307 | if (result) { |
| 308 | return count; |
| 309 | } else { |
| 310 | int num_ops = (end - start) / 2; |
| 311 | return total(num_ops) - count; |
| 312 | } |
| 313 | } |
| 314 | |
| 315 | public static void main(String[] args) { |
| 316 | String terms = "0^0|1&1^1|0|1"; |