本周题目

如果给你一个字符串，它只包含下面的几个字符:’(‘、’)’、’{‘、’} ’、’[’、‘]’，你需要判断输入的字符串是否是一个有效的圆括号字符串。例如“（（（[[]]）））”是有效的，但是“{{}”和“((”则不是。

提示

根据经验，必须选用一种最合适的STL容器来完成该题，必须写上测试代码。

输入一个括号字符串，依次检验，若为左括号则则入栈，若为右括号则出栈一个字符判断是否与之相对应，在最后还需判断栈是否为空，如果不为空则不匹配。

首先回顾栈的基本知识：

定义栈的结构体并初始化一个新栈：

struct stack
{
    char strstack[stacksize];
    int top;
};

void InitStack(stack &s)
{
    s.top=-1;
}

出栈和入栈操作：

char Push(stack &s,char a)
{
    if(s.top==stacksize-1)
    {
        return 0;
    }
    s.top++;
    s.strstack[s.top]=a;
    return a;
}

char Pop(stack &s)
{
    if(s.top==-1)
    {
        return 0;
    }
    char a=s.strstack[s.top];
    s.top--;
    return a;
}

判断栈是否为空：

#这步用来检测单个右括号的情况
int Empty(stack &s,int re)
{
    if(s.top==-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

以上是栈的基本操作，定义一个栈和初始化一个新栈，出栈和入栈操作，以及判断栈是否为空的情况。接下来将写一个函数，检查字符串的每个字符，左括号则进行入栈操作，右括号则进行出栈操作看其是否匹配，最后判断是否为空以判定是否匹配。代码如下：

int Check(char *str)
{
    stack s;
    InitStack(s);
    int strn=strlen(str);
    for(int i=0;i<strn;i++)
    {
        char a=str[i];
        switch (a)
        {
        case '(':
        case '[':
        case '{':
            Push(s,a);
            break;
        case ')':
            if(Pop(s)!='(')
            {
                return 0;
            }
            break;
        case ']':
            if(Pop(s)!='[')
            {
                return 0;
            }
            break;
        case '}':
            if(Pop(s)!='{')
            {
                return 0;
            }
            break;
        }
    }
    int re=0;
    re=Empty(s,re);
    if(re==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

自此，括号字符串匹配的判断问题已经解决， 以下是运行截图，GCC的编译结果

output.png