NYOJ2—括號配對問題

括號配對問題

時間限制：3000 ms ?|? 內存限制：65535 KB

難度：3

描述

現在，有一行括號序列，請你檢查這行括號是否配對。

輸入

第一行輸入一個數N（0<N<=100）,表示有N組測試數據。后面的N行輸入多組輸入數據，每組輸入數據都是一個字符串S(S的長度小于10000，且S不是空串），測試數據組數少于5組。數據保證S中只含有"[", "]", "(", ")" 四種字符

輸出

每組輸入數據的輸出占一行，如果該字符串中所含的括號是配對的，則輸出Yes,如果不配對則輸出No

樣例輸入

3
[(])
(])
([[]()])

樣例輸出

No
No
Yes
算法：
采用棧這種數據結構，遍歷字符串遇到'('和'['的時候放入棧中，遇到')'和']'的時候取出棧頂元素進行對應的匹配，匹配上了就出棧，直到遍歷完成，如果棧中還有剩余的元素沒有出棧，那么輸出NO否則輸出Yes
下面我們來看一下具體的代碼

 1 #include <iostream>
 2 #include<string.h>
 3 #include<stack>
 4 using namespace std;
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     while(n--)
10     {
11         char a[10010];
12         cin>>a;
13         int i,l;
14         l=strlen(a);
15         if(l%2==1)//字符個數為奇數則肯定不匹配
16         {
17             cout<<"No"<<endl;
18             continue;
19         }
20         stack <char> s;
21         for(i=0;i<l;i++)
22         {
23             if(a[i]=='('||a[i]=='[')
24             {
25                 s.push(a[i]);
26             }
27             else
28             {
29                 if(!s.empty()&&s.top()=='('&&a[i]==')')
30                 {
31                     s.pop();
32                     continue;
33                 }
34                 if(!s.empty()&&s.top()=='['&&a[i]==']')
35                 {
36                     s.pop();
37                     continue;
38                 }
39             }
40         }
41         if(!s.empty())
42         {
43            cout<<"No"<<endl;
44             continue;
45         }
46         else
47         {
48            cout<<"Yes"<<endl;
49             continue;
50         }
51     }
52     return 0;
53 }

若有不足和錯誤之處，歡迎兄弟們拍磚指正！！！

轉載于:https://www.cnblogs.com/yinbiao/p/8280140.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/252518.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/252518.shtml
英文地址，請注明出處：http://en.pswp.cn/news/252518.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！