平衡支架 - 堆栈未被识别为空

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; 
    } 
}