本周題目

如果給你一個字符串，它只包含下面的幾個字符:’(‘、’)’、’{‘、’} ’、’[’、‘]’，你需要判斷輸入的字符串是否是一個有效的圓括號字符串。例如“（（（[[]]）））”是有效的，但是“{{}”和“((”則不是。

提示

根據(jù)經(jīng)驗，必須選用一種最合適的STL容器來完成該題，必須寫上測試代碼。

輸入一個括號字符串，依次檢驗，若為左括號則則入棧，若為右括號則出棧一個字符判斷是否與之相對應(yīng)，在最后還需判斷棧是否為空，如果不為空則不匹配。

首先回顧棧的基本知識：

定義棧的結(jié)構(gòu)體并初始化一個新棧：

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

以上是棧的基本操作，定義一個棧和初始化一個新棧，出棧和入棧操作，以及判斷棧是否為空的情況。接下來將寫一個函數(shù)，檢查字符串的每個字符，左括號則進行入棧操作，右括號則進行出棧操作看其是否匹配，最后判斷是否為空以判定是否匹配。代碼如下：

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

自此，括號字符串匹配的判斷問題已經(jīng)解決， 以下是運行截圖，GCC的編譯結(jié)果

output.png