C++中的布尔括号

布尔圆括号问题是要计算给定二进制表达式加括号的方法数，以便它的计算结果为true。C++中的布尔括号

我根据给出的解释here（small video explanation here）写了一个C++解决方案，但它总是返回零。我的代码看起来与第一页上给出的代码非常相似（在写我的代码之前我没有看过），但它在我的地方没有的地方有效。我犯了什么错误？

#include <iostream> 
#include <vector> 
#include <map> 
#include <queue> 
#include <algorithm> 

using namespace std; 

int main() { 
    int n; 
    cin >> n; 

    vector<int> vals(n); 
    vector<int> ops(n - 1); //ops[n] is the operator 
          //between the nth and (n-1)th values 
    char tmp; 

    for(int i = 0; i < 2 * n - 1; ++i) { 
     if(i % 2 == 0) { 
      cin >> vals[i/2]; 
     } else { 
      cin >> ops[i/2]; 
     } 
    } 

    vector<vector<int> > t(n, vector<int>(n, 0)), 
         f(n, vector<int>(n, 0)); 

    for(int i = 0; i < n; ++i) { 
     t[i][i] = vals[i] == 1; 
     f[i][i] = vals[i] == 0; 
    } 

    const int AND = 6, OR = 1, XOR = 4; 

    for(int i = 0; i < n - 2; ++i) { 
     for(int j = i + 1; j < n - 1; ++j) { 
      for(int k = i; k < j; ++k) { 
       cout << endl << i << " " << j << " " << k << endl; 
       switch(ops[k]) { 
        case AND: 
         t[i][j] = t[i][k] * t[k + 1][j]; //T & T = T 
         f[i][j] = f[i][k] * f[k + 1][j] //F & F = F 
           + f[i][k] * t[k + 1][j] //F & T = F 
           + t[i][k] * f[k + 1][j]; //T & F = F 

        case OR: 
         t[i][j] = t[i][k] * t[k + 1][j] //etc 
           + f[i][k] * t[k + 1][j] 
           + t[i][k] * f[k + 1][j]; 
         f[i][j] = f[i][k] * f[k + 1][j]; 

        case XOR: 
         t[i][j] = f[i][k] * t[k + 1][j] 
           + t[i][k] * f[k + 1][j]; 
         f[i][j] = f[i][k] * f[k + 1][j] 
           + t[i][k] * t[k + 1][j]; 
       } 

       for(int i = 0; i < n; ++i) { 
        for(int j = 0; j < n; ++j) { 
         cout << t[i][j] << " "; 
        } 
        cout << endl; 
       } 
      } //k loop 
     } //j loop 
    } //i loop 

    cout << endl << t[0][n - 1]; 
}

来源

2014-12-06 Soham Chowdhury

编译所有警告和调试信息（例如'g ++ -Wall -Wextra -g'）。学习如何**使用调试器**（例如'gdb'） – 2014-12-06 06:38:12

是的，但我并没有发现任何错误。。。在这种情况下，我可以用'gdb'做什么？ – 2014-12-06 06:39:23

用调试器可以做什么：检查过程的状态，查询变量和调用框架并逐步运行;想想你的计划;明白什么是错的;改进你的程序;重新编译;并重复，直到你满意为止。 – 2014-12-06 06:40:34

外两个环路（i和j）不是正确的。你在代码中做的是从表达式的一端开始，向另一端（i循环）移动，并尝试计算从当前位置开始的越来越宽的子表达式（宽度为j - i,j循环）。问题是，为了计算宽度为k的表达式的括号变化，您需要所有其子表达式的宽度为k - 1和更小的值，在您的解决方案中，您尚未计算（不是所有值，无论如何）。因此，您依赖的是尚未计算出的值，并且默认为0，这会在这些乘法运算中给出不错的零值。

与任何动态规划问题，关键是要建立宽度k所有值仅后您计算出所有相关值宽度k - 1。因此，外两个循环应该是这个样子：

//You've calculated width 0 in the loop before, so start at 1. 
for(int width = 1; width < n; ++width) 
    for(int i = 0, j = i + width; j < n; ++i, ++j) 
     //The inner loop looks OK at first glance, 
     //but I haven't looked at it in depth.

请记住，这是未经检验，未实现代码，它只是基于我在这种情况下，动态规划问题的理解（我的理解一直已知不时会出错......）。但是，它应该让您在清理问题方面领先一步。

来源

2014-12-06 17:04:50 bogdan

C++中的布尔括号

回答

相关问题