括号配对问题

港控/mmm° 2022-06-16 07:30 361阅读 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

来源

[网络][Link 1]

上传者

[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 <stack> 的头文件来调用它。**

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

#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;
    }

通过这个我学到了很多，以前学数据结构，但不知道该怎么用它，这个案例给我做了一个实例。算是一点进步吧。 ![大笑][laugh.gif] ![大笑][laugh.gif] ![大笑][laugh.gif]

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%BD%91%E7%BB%9C
[naonao]: http://acm.nyist.net/JudgeOnline/profile.php?userid=naonao
[laugh.gif]: /images/20220616/bb75fadfe992420582f88062eb018573.png