首页 > 代码库 > 9.11 给定一个布尔表达式，由0、1、&、|、^等符号组成，以及一个想要的布尔结果result，实现一个函数，算出有几种括号的放法可使该表达式得出result的值。
9.11 给定一个布尔表达式，由0、1、&、|、^等符号组成，以及一个想要的布尔结果result，实现一个函数，算出有几种括号的放法可使该表达式得出result的值。
思路： 枚举分割点递归求解，可用DP优化。
注意递归终止条件。
注意 ^ & | 三种情况统计的不同。
import java.util.HashMap;import java.util.Map;public class Solution { int countR(String terms, boolean result, int start, int end, Map<String, Integer> cache) { String key = "" + result + start + end; if (cache.containsKey(key)) { return cache.get(key); } if (start == end) { if (terms.charAt(start) == ‘0‘) { if (result) return 0; else return 1; } else { if (result) return 1; else return 0; } } int count = 0; if (result) { for (int i = start + 1; i < end; i++) { char op = terms.charAt(i); if (op == ‘&‘) { count += countR(terms, true, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); } else if (op == ‘|‘) { count += countR(terms, true, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); count += countR(terms, true, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); count += countR(terms, false, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); } else if (op == ‘^‘) { count += countR(terms, true, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); count += countR(terms, false, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); } } } else { for (int i = start + 1; i < end; i++) { char op = terms.charAt(i); if (op == ‘&‘) { count += countR(terms, true, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); count += countR(terms, false, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); count += countR(terms, false, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); } else if (op == ‘|‘) { count += countR(terms, false, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); } else if (op == ‘^‘) { count += countR(terms, true, start, i - 1, cache) * countR(terms, true, i + 1, end, cache); count += countR(terms, false, start, i - 1, cache) * countR(terms, false, i + 1, end, cache); } } } cache.put(key, count); return count; } public static void main(String[] args) { String terms = "0^0|1&1^1|0|1"; boolean result = true; Map<String, Integer> cache = new HashMap<String, Integer>(); System.out.println(new Solution().countR(terms, result, 0, terms.length() - 1, cache)); }}
9.11 给定一个布尔表达式，由0、1、&、|、^等符号组成，以及一个想要的布尔结果result，实现一个函数，算出有几种括号的放法可使该表达式得出result的值。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。