栈的应用：括号匹配

题目：给定一个字符串，其中的字符只包含三种括号：花括号{ }、中括号[ ]、圆括号( )，即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法，判断该字符串是否匹配。括号匹配要求括号必须以正确的顺序配对，如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式，而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

首先，不能考虑从每种括号的数量上进行匹配，比如对于 “[ ( ] )”，虽然中括号和圆括号在数量上是匹配的，但它们的顺序却不匹配。 其次，如果站在左括号的角度，下一个与其匹配的右括号位置不固定，即左括号的下一个既可能是左括号，也可能是右括号，考虑起来很麻烦。但是站在右括号角度就方便许多。我们可以发现一个特点，如果字符串想要匹配，第一个右括号的左侧一定是一个与之匹配的左括号。这样，我们可以从左往右检索字符串，遇到左括号就存在缓冲区里，遇到右括号就和最后进入缓冲区的那个字符比较。这里用到了栈的数据结构。

代码如下：

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

//判断字符是左括号还是右括号
int isleft(char c)
{
    if(c=='('||c=='['||c=='{') return 1;//是左括号，返回1
    if(c==')'||c==']'||c=='}')return 0;//是右括号，返回0
}
//把左括号转换成相对应的右括号用以比较是否匹配
char rev(char c)
{
    if(c=='(') return ')';
    if(c=='[') return ']';
    if(c=='{') return '}';
}

int main()
{
    //freopen("input.txt","r",stdin);
    char s[100];
    while(scanf("%s",s)!=EOF)
    {
        char stack[100];int top=0;//定义栈，初始化栈顶
        int flag=0;//用来标识是否匹配的变量，默认匹配
        int i;int len=strlen(s);
        for(i=0;i<len;i++)
        {
            if(isleft(s[i])==1)//如果是左括号就入栈
            {
                stack[top]=s[i];
                top++;
            }
            if(isleft(s[i])==0)//如果是右括号
            {
                if(s[i]==rev(stack[top-1]))//如果右括号和栈顶匹配，出栈
                    top--;
                else//如果右括号和栈顶不匹配（包括了第一个字符是右括号的情形）
                {
                    flag=1;//不匹配
                    break;//一定不匹配，后面就不用比较了
                }
            }
        }

        if(flag==1)//不匹配
            printf("NO\n");
        else//匹配（匹配的条件也可以用栈顶等于0来判断）
            printf("YES\n");

    }

    return 0;
}