STL：stack堆栈容器及例题括号配对问题

59 阅读 0 评论 39 点赞

我是靠谱客的博主孝顺朋友，最近开发中收集的这篇文章主要介绍STL：stack堆栈容器及例题括号配对问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、stack堆栈容器
1、后进先出；
2、插入元素的一端称为栈顶（Stack Top），另一端称为栈底（Stack Bottom）；
3、插入元素叫入栈（Push），元素删除称为出栈（Pop）；
4、头文件要有#include;
5、采用push()方法将元素入栈；采用top()方法访问栈顶元素；采用empty()方法判断堆栈是否为空，如果是空的，则返回逻辑真，否则返回逻辑假；采用size()方法返回当前堆栈中有几个元素。
二、括号配对问题
描述
现在，有一行括号序列，请你检查这行括号是否配对。
输入
第一行输入一个数N（0<N<=1000），表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S（S的长度小于10000，且S不是空串），测试数据组数不少于5组。数据保证S中只含有"[","]","(",")"四种字符
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
样例输出

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

样例输出

No
No
Yes

具体代码

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int main()
{
    int n;
    char s[50];
    stack<char>st;//建立字符型栈
    cin>>n;
    while(n--)
    {
        cin>>s;
        while(!st.empty())
        {
            st.pop();
        }
        int len=strlen(s),flag=1;
        for(int i=0;i<len;i++)
        {
            if(s[i]=='('||s[i]=='[')
                st.push(s[i]);
            else
                {
                    if(st.empty())
                    {
                        flag=0;
                        break;
                    }
                    char t=st.top();
                    st.pop();
                    if(s[i]==')'&&t=='[')
                    {
                        flag=0;
                        break;
                    }
                    else if(s[i]==']'&&t=='(')
                    {
                        flag=0;
                        break;
                    }
                }
        }
        if(!st.empty())
            flag=0;
        if(flag==1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

如果S中含有"(" ,")","[" ,"]","{","}"六种字符
具体代码

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int main()
{
    int n;
    char s[50];
    stack<char>st;//建立字符型栈
    cin>>n;
    while(n--)
    {
        cin>>s;
        while(!st.empty())
        {
            st.pop();
        }
        int len=strlen(s),flag=1;
        for(int i=0;i<len;i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
                st.push(s[i]);
            else
                {
                    if(st.empty())
                    {
                        flag=0;
                        break;
                    }
                    char t=st.top();
                    st.pop();
                    if(s[i]==')'&&(t=='['||t=='{'))
                    {
                        flag=0;
                        break;
                    }
                    else if(s[i]=='}'&&(t=='('||t=='['))
                    {
                        flag=0;
                        break;
                    }
                    else if(s[i]==']'&&(t=='('||t=='{'))
                    {
                        flag=0;
                        break;
                    }
                }
        }
        if(!st.empty())
            flag=0;
        if(flag==1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}