括号匹配问题（栈的使用）

偏执的太偏执、 2021-09-22 12:44 367阅读 0赞

## 括号配对问题 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 3

**描述**

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

**输入**

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

**输出**

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

**样例输入**

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

**样例输出**

No
    No
    Yes

**代码**

#include <iostream>
    #include <string.h>
    #include <stack>
    using namespace std;
    char e[10000];
    bool match(stack<char> s,char e[],int n)
    {
        for(int i=0;i<n;i++)
        {
            if(e[i]=='('||e[i]=='[')
               s.push(e[i]);
            if(e[i]==')')
            {
                if(s.empty())//栈里没元素遇到')'肯定不能匹配
                    return 0;
                else if(s.top()=='(')//匹配，出栈
                        s.pop();
                else
                    return 0;
            }
            if(e[i]==']')
            {
                if(s.empty())
                    return 0;
                else if(s.top()=='[')
                        s.pop();
                else
                    return 0;
            }
        }
        if(s.empty())//匹配成功的条件
            return 1;
        else
            return 0;
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--)
        {
            cin>>e;
            int len=strlen(e);
            stack<char>s;
            if(match(s,e,len))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        return 0;
    }

本文转载于：https://blog.csdn.net/sr\_19930829/article/details/22983435