括号配对问题-蒲公英云

括号配对问题

港控/mmm° 2022-06-16 07:30 386阅读 0赞

括号配对问题，其实是栈的一个应用，很常见也很普通。

栈是最常见的和最重要的数据结构之一，用途非常广泛。它是一种只能在一端进行插入或删除操作的线性表，括号配对是栈的链式储存及其基本运算的实现的结果。刚学时书上有一大堆代码来实现它的基本运算。由于自己也是刚学，只会比葫芦画瓢，正好在南阳oj上看到第二题：

括号配对问题

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

难度： 3

描述

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

输入

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

输出

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

样例输入

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

样例输出

No
No
Yes

来源

网络

上传者

naonao

因为数据结构书上有一道和它类似的题，然后，我就将他的基本运算给打了上去。。。

#include <stdio.h>
#include <string.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode                               //栈链中数据节点的类型LiStack的定义
{
    ElemType data;
    struct linknode *next;
}LiStack;
void InitStack(LiStack * &s)                          //初始化栈
{
    s=(LiStack *)malloc(sizeof(LiStack));
    s ->next=NULL;
}
void DestroyStack(LiStack * &s)                       //销毁栈
{
    LiStack *p=s, *q=s ->next;
    while (q!=NULL)
    {
        free(p);
        p=q;
        q=p -> next;
    }
    free(p);
}
bool StackEmpty(LiStack *s)                            //判断栈是否为空
{
    return (s ->next==NULL);
}
void Push(LiStack * &s,ElemType e)                     //进栈
{
    LiStack *p;
    p=(LiStack *)malloc(sizeof(LiStack));
    p ->data=e;
    p ->next=s->next;
    s ->next =p;
}
bool Pop(LiStack * &s,ElemType &e)                      //出栈
{
    LiStack *p;
    if (s ->next==NULL)
        return false;
    p=s ->next;
    e=p ->data;
    s ->next=p ->next;
    free(p);
    return true;
}
bool GetTop(LiStack *s,ElemType &e)                    //取栈顶元素
{
    if (s ->next==NULL)
        return false;
    e=s ->next ->data;
    return true;
}
bool Match(char exp[],int n)                            //编写了一个括号配对的函数
{
    int i=0;char e;
    bool match=true;
    LiStack *st;
    InitStack(st);
    while (i<n && match)
    {
        if (exp[i]=='(' || exp[i]=='[')
            Push(st,exp[i]);
        else if (exp[i]==')')
        {
            if (GetTop(st,e)==true)
            {
                if (e!='(')
                    match = false;
                else
                    Pop(st,e);
            }
            else match=false;
        }
        else if (exp[i]==']')
        {
            if (GetTop(st,e)==true)
            {
                if (e!='[')
                    match = false;
                else
                    Pop(st,e);
            }
            else match=false;
        }
        i++;
    }
    if (!StackEmpty(st))
        match = false;
    DestroyStack(st);
    return match;
}
int main()                                                             //主函数
{
    int len,t;
    ElemType str[10005];
    scanf("%d",&t);
    while (t--)
    {
        scanf("%s",str);
        len=strlen(str);
        if (Match(str,len)==true)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

真的是很长很长的一段代码，不过很幸运竟然ac了，正当我高兴的时候，我看了那上面的最优代码，发现上面的代码比我的要短很多很多，为什么会这样，为此我问了我的数据结构老师，我才知道其实那些基本运算在codeblock上都是有的（我一直用的codeblock写代码），只需你写一个

#include 的头文件来调用它。

于是代码就有了很大的改进：

#include <iostream>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
    int t,i,n;
    char a[10005];
    cin>>t;
    while (t--)
    {
        stack<char>str;                                              //调用栈
        scanf("%s",a);
        n=strlen(a);
        for (i=0;i<n;i++)
        {
            if (str.empty())                                         //判断是否为空
                str.push(a[i]);
            else
            {
                if (str.top()+1==a[i]||str.top()+2==a[i])
                    str.pop();                                        //如果配对那就让栈顶元素出栈
                else
                    str.push(a[i]);
            }
        }
        if (str.empty())                                              //如果栈中没有元素则输出yes
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}