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++中的布爾括號

回答

相關問題