ACM在线练习-括号配对问题

括号配对问题

描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

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

样例输出

No
No
Yes

思路:模拟栈进行操作

如果输入[,(则将它们入栈,当前输入字符如果是右括号且与紧邻上一个字符匹配,则将紧邻的上一个字符出栈,如果不匹配则括号序列出错.

如果进行的一系列匹配操作过程不出错,则最后栈为空,即是正确的括号序列.

#include<iostream>
using namespace std;
struct Stack
    {
        char str[100];
        int i;//入栈的编号
    };
int main()
{
    int N;
    char c;
    Stack stack;
    cin>>N;
    getchar();
    while(N)
    {
        stack.i=-1;
        while((c=getchar())!='\n')
        {
            if(c=='['||c=='(')
                stack.str[++stack.i]=c;
            else if((stack.str[stack.i]=='['&&c==']')||(stack.str[stack.i]=='('&&c==')'))
                stack.i--;
            else
                {
                    stack.i=0;
                    break;
                }
        }
        if(stack.i==-1)
        cout<<"yes"<<endl;
        else
        cout<<"no"<<endl;
        N--;
    }
    return 0;
}

描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

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

样例输出

No
No
Yes

思路:模拟栈进行操作

如果输入[,(则将它们入栈,当前输入字符如果是右括号且与紧邻上一个字符匹配,则将紧邻的上一个字符出栈,如果不匹配则括号序列出错.

如果进行的一系列匹配操作过程不出错,则最后栈为空,即是正确的括号序列.

#include<iostream>
using namespace std;
struct Stack
    {
        char str[100];
        int i;//入栈的编号
    };
int main()
{
    int N;
    char c;
    Stack stack;
    cin>>N;
    getchar();
    while(N)
    {
        stack.i=-1;
        while((c=getchar())!='\n')
        {
            if(c=='['||c=='(')
                stack.str[++stack.i]=c;
            else if((stack.str[stack.i]=='['&&c==']')||(stack.str[stack.i]=='('&&c==')'))
                stack.i--;
            else
                {
                    stack.i=0;
                    break;
                }
        }
        if(stack.i==-1)
        cout<<"yes"<<endl;
        else
        cout<<"no"<<endl;
        N--;
    }
    return 0;
}