題目描述:
現在,有一行括號序列,請你檢查這行括號是否配對。
輸入描述:
第一行輸入一個數N(0<N<=100),表示有N組測試數據。后面的N行輸入多組輸入數據,每組輸入數據都是一個字符串S(S的長度小于10000,且S不是空串),測試數據組數少于5組。數據保證S中只含有"[", “]”, “(”, “)” 四種字符
輸出描述:
每組輸入數據的輸出占一行,如果該字符串中所含的括號是配對的,則輸出Yes,如果不配對則輸出No
樣例輸入:
3
[(])
(])
([])
樣例輸出:
No
No
Yes
思路分析:
對于括號匹配問題,這里運用C++的棧操作,比較方便。
定義一個變量y,用來判斷是否匹配成功,若成功,y=1,否則,y=0;最后根據y的值來輸出最后的結果。
定義一個字符數組s,存儲輸入的符號
定義一個變量l,為字符數組s的最大長度
定義一個變量n,為需要判斷的組數
定義一個字符類型的棧sq,判斷是字符數組s里面的元素符號是否是‘(’,‘{’,‘[’,若是左半邊符號,則入棧,
如不是,則跟已經入棧的棧頂元素進行匹配,
若匹配失敗,y=1,結束本次判斷;
若匹配成功,則將該元素符號出棧
最后組數循環完之后,判斷棧是否為空,是否全都匹配成功出棧了,若棧不為空,則y=1,匹配失敗。然后將棧中其他元素全部出棧。
代碼如下:
#include <iostream>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;int main()
{int n,i,l,y=0; //l為字符數組s的大小長度;y=1表示匹配失敗,y=0表示匹配成功char s[65536]; //定義一個字符數組用來存待匹配的符號stack<char>sq; //定義一個char類型的棧scanf("%d",&n); //輸入要測試的幾組數據while(n--){y=0; //這里的y用來判斷是否為空棧cin>>s;l=strlen(s);for(i=0;i<l;i++){if(s[i]=='('||s[i]=='{'||s[i]=='[') //如果字符數組s里面的字符為左半邊符號sq.push(s[i]); //該字符數組s里面的符號進棧else{if(sq.empty()) //如果棧為空{y=1; //y=1,直接說明匹配不成功,因為根本沒有進左括號break;}}if(s[i]==']') //判斷字符數組里面的元素是否是 ] ,如果是進入下一個判斷{if(sq.top()!='[') //判斷棧頂是否是 [{y=1; //若不是 [ y=1,匹配失敗break; //結束}else sq.pop(); //若是 [ 將棧頂元素出棧}if(s[i]=='}') //以次類推{if(sq.top()!='{'){y=1;break;}else sq.pop();}if(s[i]==')'){if(sq.top()!='('){y=1;break;}else sq.pop();}}if(!sq.empty()) //最后,如果棧不為空,則匹配失敗{y=1;}if(y==1) printf("No\n");else printf("Yes\n");while(!sq.empty()) //如果棧不空,棧頂元素出棧,直到棧為空為止{sq.pop();}
}return 0;}