问题
给定一个由符号 0, 1, &, |, ^
和所需 bool 结果值组成的 bool 表达式,实现一个函数来计算将表达式括起来的方式数量,以便计算结果.
示例
表达式 1^0|0|1
期望结果 0
输出 2, 1^((0|0)|1), 1^(0|(0|1))
我的想法是使用回溯,并计算a运算符b
形式的表达式。例如
1^0|0|1
--------
0123456
有 3 种可能的评估:0, 2, 4
,更具体地说,我有:
(1)
在 0 -> 1|0|1
处评估
(2)
在 0 -> 1|1
处评估
(3)
在 0 -> 1
处评估
然后我在(2)
处回溯,在位置2
处求值...这个想法很简单,但它产生了重复的结果。 result = 1
的方法数量应为 3
,但我的方法产生 4
。
bool evaluate(const string& expr) {
assert(expr.length() == 3);
assert(expr[0] == '0' || expr[0] == '1');
assert(expr[1] == '^' || expr[1] == '|' || expr[1] == '&');
assert(expr[2] == '0' || expr[2] == '1');
bool result;
bool a = (expr[0] == '1' ? 1 : 0);
bool b = (expr[2] == '1' ? 1 : 0);
switch (expr[1]) {
case '^' :
result = a ^ b;
break;
case '|' :
result = a | b;
break;
case '&' :
result = a & b;
break;
}
return result;
}
void transform_at(string& s, int start) {
bool result = evaluate(s.substr(start, 3));
string left = s.substr(0, start);
string right = s.substr(start + 3);
result ? left.append(1, '1') : left.append(1, '0');
s = left + right;
}
int count_parenthese_grouping(string expr, const bool result) {
cout << "[recurse on]: " << expr << endl;
if (expr.length() == 3 && evaluate(expr) == result) {
return 1;
}
else if (expr.length() == 3 && evaluate(expr) != result) {
return 0;
}
else {
int operators = expr.length() - 2;
int total = 0;
for (int i = 0; i < operators; i += 2) {
string temp = expr;
transform_at(expr, i);
total += count_parenthese_grouping(expr, result);
expr = temp;
}
return total;
}
}
我看不出这个解决方案如何生成重复的结果!有人可以帮我吗?
最佳答案
重复是因为您可以通过两种方式得出 (1^0)|(0|0):首先,将 1^0 加上括号,然后将 0|0 加上括号;其次,将 0|0 加括号,然后加括号 1^0。
您需要确保相同的括号只计算一次。
一种可能的方法是根据括号计算一个标识号,然后维护一组这些标识号,并且只计算尚未包含在该组中的标识号。
这种 id 的一种可能性是以位模式表示括号:前 n-1 位表示第一级括号,接下来的 n-2 位表示第二级括号(括号包含第一级括号)等
例如
(1^0)|0|0 would become 10000
1^(0|0)|0 would become 01000
1^0|(0|0) would become 00100
(1^0)|(0|0) would become 10100
(1^(0|0))|0 would become 01010
1^((0|0)|0) would become 01001
关于c++ - 这种情况下如何正确回溯呢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11025083/