平衡支架 - 堆棧未被識別爲空

Question

這讓我有點慌亂。我花了很長的時間試圖找出錯誤，但卻不能。問題是要確定給定的括號內的輸入字符串是否平衡。當它返回1時，輸入'{[（）（）]}'返回0。下面的代碼實際上並沒有達到返回1部分，但我不明白爲什麼不 - 到那時棧應該是空的。有任何想法嗎？

#include <stack> 

int solution(string &S) { 

stack<char> bracketStack; 
char a, b, c; 

for (int i = 0; i < S.length(); i++) { 
    if (S[i]=='{' || S[i]=='[' || S[i]=='(') { 
     bracketStack.push(S[i]); 
    } else { 
     switch (S[i]) { 
     case ('}') : 
      a = bracketStack.top(); 
      bracketStack.pop(); 
      if (a==']' || a==')') { 
       return 0; 
      } 
     case (']') : 
      b = bracketStack.top(); 
      bracketStack.pop(); 
      if (b=='}' || b==')') { 
       return 0; 
      } 
     case (')') : 
      c = bracketStack.top(); 
      bracketStack.pop(); 
      if (c==']' || c=='}') { 
       return 0; 
      } 
     } 
    }  
} 

if (bracketStack.empty()) { 
    cout << "empty"; 
    return 1; 
} else { 
    return 0; 
} 

} 

Answer 1

你的代碼邏輯有錯誤：呼叫

a = bracketStack.top(); // or b, or c 

的switch所有三個部門內部沒有被檢查堆棧非空保護。這會導致未定義的行爲（從堆棧的無效元素讀取）當有更多的右括號比打開的。

解決此問題將解決您遇到的問題。但是，您的程序仍然不是最佳的，因爲這三個分支看起來幾乎完全相同。您可以通過將開關組合如下來解決此問題：

// Set up an array of matching brackets: } --> {, ] --> [,) --> (
char match[128] = {0}; 
match['}'] = '{'; 
match[']'] = '['; 
match[')'] = '('; 

... // This goes inside the `for` loop 
if (S[i]=='{' || S[i]=='[' || S[i]=='(') { 
    bracketStack.push(S[i]); 
} else { 
    if (bracketStack.empty()) { 
     cout << "More closing brackets than opening ones" << endl; 
     return 0; 
    } 
    a = bracketStack.top(); 
    bracketStack.pop(); 
    if (match[a] != S[i]) { 
     cout << "Mismatched" << endl; 
     return false; 
    } 
}