****Description**
输入一个包含“()”和“[]”的括号序列,判断是否合法。 具体规则:
– 空串合法;
– 如果A和B都合法,则AB合法
– 如过A合法则(A)和[B]都合法

Sample Input

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

Sample Output

Yes
No
Yes

题解:
他说什么AB合法之类的,其实都是空串。。。
我想得太复杂了。。
然后我们可以开一个栈
每读入一个字符,如果是 ) 或 ] 就和栈顶元素比较
看是不是对应的字符,如果是就弹出栈顶
如果栈是空的话,或者说读入字符是 ( 或 [ 的话,直接进栈就好了

Code

#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    int n=read();
    while(n--){
        stack<char >s;char ch;
        while(ch=getchar()){
            if(ch=='\n')break;
            if(ch=='('||ch=='[')s.push(ch);
            if(s.empty())s.push(ch);
            if((!s.empty())&&((ch==')'&&s.top()=='(')||(ch==']'&&s.top()=='[')))s.pop();
        }
        if(s.empty())puts("Yes");else puts("No");
    }
    return 0;
}

发表评论