括號配對問題
描述
現在,有一行括號序列,請你檢查這行括號是否配對。
輸入
第一行輸入一個數N(0<N<=100),表示有N組測試數據。後面的N行輸入多組輸入數據,每組輸入數據都是一個字符串S(S的長度小於10000,且S不是空串),測試數據組數少於5組。數據保證S中只含有"[","]","(",")"四種字符
輸出
每組輸入數據的輸出占一行,如果該字符串中所含的括號是配對的,則輸出Yes,如果不配對則輸出No
樣例輸入
3
[(])
(])
([[]()])
樣例輸出
No
No
Yes
我的程序,采用語言c++。
思路:將未匹配字符入棧,沒當有匹配字符,出棧。最後檢測棧是否為空即可。
源碼已經過在線系統驗證。
SyntaxMatch.cpp
[cpp]
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
int nLineNum = 0;
cin>>nLineNum;
if(nLineNum<0 || nLineNum>100)
{
cout<<"Please input number 0<n<=100."<<endl;
return 1;
}
vector<string> vInputList;
for(int i=0; i<nLineNum; ++i)
{
string sInputStr="";
cin>>sInputStr;
if(sInputStr.size() == 0)
{
cout<<"Error:Input string is empty."<<endl;
--i;
continue;
}
if(sInputStr.size() >=10000)
{
cout<<"Error:Input string is too long."<<endl;
--i;
continue;
}
vInputList.push_back(sInputStr);
}
vector<string>::iterator vIter = vInputList.begin();
for(; vIter != vInputList.end(); ++vIter)
{
string sUnMatch="";
string sInput=*vIter;
string::iterator sIter = sInput.begin();
for(; sIter != sInput.end(); ++sIter)
{
char cCurChar = *sIter;
if(sUnMatch.empty())
{
sUnMatch.push_back(cCurChar);
}
else
{
string::iterator sEndIter = sUnMatch.end() - 1;
char cEndChar=*sEndIter;
if((cEndChar=='[' && cCurChar==']')
||(cEndChar=='(' && cCurChar==')'))
{
sUnMatch.erase(sEndIter);
}
else
{
sUnMatch.push_back(cCurChar);
}
}
}
if(sUnMatch.empty())
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 1;
}