数据结构栈与队列（一）括号匹配

数据结构（四）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 括号匹配 ——

1.题目描述

Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号()、中括号[]和大括号{}，总长度为N。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的：
(1) 空的括号序列是美观的；
(2) 若括号序列A是美观的，则括号序列(A)、[A]、{A}也是美观的；
(3)若括号序列A、B都是美观的，则括号序列AB也是美观的；例如 (){[]}() 是美观的括号序列，而 )({)[}]( 则不是。
现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗？

1.1输入

一个括号序列，长度不超过10000。

1.2输出

如果它是美观的，输出Yes，否则输出No。

1.3样例输入和输出

样例输入
{ } ( ) { [ ] } ( )
样例输出
Yes

2.代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char ElemType;

typedef struct{
     //存储元素的数组
     ElemType *base;
     //栈顶指针
     int top;
     //当前分配的存储容量( 以sizeof(ElemType)为单位 )
     int capacity;

}Stack;
//初始化一个空栈。空栈拥有10000个元素的空间，栈顶值为 -1
void init(Stack *pStack)
{
    pStack->base=(ElemType*)malloc(10*sizeof(ElemType));
    pStack->capacity=10;
    pStack->top=-1;
}
//把x入栈
void push(Stack *pStack,ElemType x)
{
    //如果输入的元素即将超出栈的最大限制，那么进行扩容。
    if(pStack->top==pStack->capacity-1)
    {
        //以原来容量的两倍进行扩容.
        pStack->capacity*=2;
        ElemType*b=(ElemType*)malloc(pStack->capacity*sizeof(ElemType));
        //复制数据到新的扩容后的栈中数组
        for(int e=0;e<=pStack->top;e++)
        {
            b[e]=pStack->base[e];
        }
        free(pStack->base);
        pStack->base=b;
    }
    //如果输入的元素没有超出栈的最大限制，那么将元素压栈
    pStack->base[++pStack->top]=x;
}
//返回当前栈顶元素的值
ElemType top(Stack *pStack)
{
    ElemType f=pStack->base[pStack->top];
    return f;
}
//当前栈顶元素出栈
void pop(Stack *pStack)
{
    pStack->top--;
}
//判断是否栈空，若空则返回 true，否则返回 false
bool empty(Stack *pStack)
{
    if(pStack->top==-1)
        return true;
    else
        return false;
}
//清空分配给栈的存储空间
void destroy(Stack *pStack)
{
    free(pStack->base);
    free(pStack);
}
int main(void)
{
    char c[10000];
    Stack *pStack;
    pStack=(Stack*)malloc(sizeof(Stack));
    init(pStack);
    bool flag=true;
    gets(c);
    for(int i=0;c[i]!='\0';i++)
        {
            if(c[i]=='('||c[i]=='['||c[i]=='{')
                push(pStack,c[i]);

            if(c[i]==')'||c[i]==']'||c[i]=='}')
            {
                if(empty(pStack))
                {
                    printf("No\n");
                    flag = false;
                    break;
                }
                else
                {
                    if((c[i]==')'&&pStack->base[pStack->top]=='(')||
                       (c[i]==']'&&pStack->base[pStack->top]=='[')||
                       (c[i]=='}'&&pStack->base[pStack->top]=='{'))
                       {
                            pop(pStack);
                            continue;
                       }
                    else
                       {
                           printf("No\n");
                           flag=false;
                           break;
                       }
                }
            }
        }
        if(flag==true)
        {
            if(empty(pStack))
                printf("Yes\n");
            else
                printf("No\n");
        }
        destroy(pStack);
    return 0;
}

3.代码说明

这道题虽然说什么美观的括号，但其实就是利用栈实现括号的匹配，那我们首先就要搞清楚括号匹配和不匹配的类型：
1.==匹配的类型就一种==，我们利用栈的先进后出的特性，对括号从最内侧进行匹配，如果到最后一个元素输入后，整个栈中没有元素（匹配后元素就直接出栈删除）的话，就是匹配的，输出“Yes”。
2.==不匹配的类型有三种==
2.1左括号多余，也就是说在输入数据结束后，最后一个元素是括号的左半部分“（”，“{”，“[”。那么这个时候就是输出“No”。
2.2右括号多余，也就是说在输入数据结束后，最后一个元素是括号的右半部分“）”，“}”，“]”。那么这个时候就是输出“No”。
2.3括号不匹配，也就是说在输入数据结束后，栈内元素的括号不能相互匹配，例如：“（}”，“{[”，“[{)”。那么这个时候就是输出“No”。
3.其实==大体思路==就是每输入一个数据就对前一个数据进行匹配，如果匹配成功就一起出栈，如果到最后栈内没有数据了，那就是yes，反之就是No。
4.具体写第二条是因为，有些题目会要求细分为具体不匹配的原因，例如下面这题：

描述

假设表达式中只包含三种括号：圆括号、方括号和花括号，它们可相互嵌套，如([{}])或({[][()]})等均为正确的格式,而{[]})}或{[()]或([]}均为不正确的格式.
输入一串括号
如果输入的右括号多余，输出:Extra right brackets
如果输入的左括号多余,，输出:Extra leftbrackets
如果输入的括号不匹配，输出:Brackets not match
如果输入的括号匹配，输出:Brackets match

输入

{{{{)))

输出

Brackets not match

样例输入

{([)]}

样例输出