括号配对问题

括号配对问题

描述

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

输入第一行输入一个数N$（0<N<=100）$表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有”[“, “]”, “(“, “)” 四种字符输出每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

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

样例输出

No
No
Yes

坑点

1.我写了好多次运行错误，原因是操作栈的时候，当栈空了的时候我没有做判断，还继续访问，导致出错

题解

这道题很明显是要用栈stack来写的，如果遇到 [ 或 ( 的时候进行如栈的操作，如果遇到 ] 和 ) 的时候，进行出栈，然后进行比较，如果出栈的内容与刚刚的相同则继续比较，如果不相同，则跳出循环，然后输出No，当整个字符串遍历完以后，如果没有跳出，则输出Yes。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

char judge(char ch)
{
    if(ch == ')')
    {
        return '(';
    }
    else
    {
        return '[';
    }
}

int main()
{
    string str;
    stack<char> s;
    int m;
    int len;
    cin>>m;
    while(m--)
    {
        bool flag = true;
        cin>>str;
        len = str.length();
        if(len % 2 == 1)
        {
            cout << "No" << endl;
            continue;
        }
        for(int i = 0; i < len; i++)
        {
            if(str[i] == '[' || str[i] == '(')
            {
                s.push(str[i]);
            }
            else
            {
                if(s.empty())//防止s为空时，访问s的top
                {
                    flag = false;
                    break;
                }
                if(judge(str[i]) == s.top())
                {
                    s.pop();
                }
                else
                {
                    flag = false;
                    break;
                }
            }
        }
        while(!s.empty())//判断s是否为空，顺便清空s
        {
            flag = false;
            s.pop();
        }
        if(flag)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }

    }

    return 0;
}