括号配对问题

问题：对于给定的只含有 "(", ")", "[", "]", "{", "}" 六种字符的非空字符串，判断其括号是否配对。

思路：可用 STL 中的栈 stack 来处理。

首先先判断字符串长度的奇偶性：

1. 若为奇数，肯定不配对;

2. 若为偶数，从头到尾遍历给定的字符串：

(1) 若为 '(', '[', '{', 则入栈；

(2) 否则，判断栈是否为空：

① 若栈为空，肯定不配对；

② 否则，判断栈顶是否为其所配对的括号，若是，出栈；否则，肯定不配对；

最后判断栈是否为空，若为空，则配对；否则，不配对。

以下是 C++ 实现代码：

 1 /**************************************************************
 2 problem : 括号配对问题
 3 author  : 林秋伟
 4 time    : 2013-10-26
 5 **************************************************************/
 6 #include <iostream>
 7 #include <string>
 8 #include <stack>
 9 using namespace std;
10 
11 bool judge(string S){
12     int len=S.size();
13     if(len&1) return 0;
14     stack<char> s;
15     for(int i=0; i<len; i++){
16         if(S[i]=='(' || S[i]=='[' || S[i]=='{') s.push(S[i]);
17         else{
18             if(s.empty()) return 0;
19             if(S[i]==')' && s.top()!='(') return 0;
20             if(S[i]==']' && s.top()!='[') return 0;
21             if(S[i]=='}' && s.top()!='{') return 0;
22             s.pop();
23         }
24     }
25     return s.empty();
26 }
27 
28 int main(){
29     string S;
30     while(cin>>S) cout<<(judge(S)? "Yes":"No")<<endl;
31     return 0;
32 }