Description
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a)
if it is the empty string
(b)
if A and B are correct, AB is correct,
(c)
if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.
Output
A sequence of Yes or No on the output file.
Sample Input
Sample Output
Yes
No
Yes
理解:
括号配对问题 , 每一对括号都有相对应的左和右的话就输出"Yes",否则"No".
需要注意的是 , 如果什么都不输入的话,也要输出"Yes" , 这也是这一题的难点.
代码部分
#include<iostream>
#include<string.h>
#include<string>
#include<stack>
using namespace std;
string s; const char *s1; double j;
stack<char>x;
stack<char>y;
int main()
{
int n;
cin>>n;
getchar();
while(n--)
{
getline(cin,s);
if(s.size()==0)
{cout<<"Yes\n";continue;}
while(!x.empty())
{
x.pop();
}
while(!y.empty())
{
y.pop();
}
s1=s.c_str();
char *s2=new char[strlen(s1)+1];
strcpy(s2,s1);
j=strlen(s2);
for(int i=0;i<strlen(s2);i++)
{
x.push(s2[i]);
}
while(!x.empty())
{
while((!x.empty()&&!y.empty())&&((x.top()=='('&&y.top()==')')||(x.top()=='['&&y.top()==']')))
{
x.pop();y.pop();
}
if(!x.empty())
{
y.push(x.top());
x.pop();
}
}
if(x.empty()&&y.empty())
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
}
}
return 0;
}
