【数据结构】栈的应用——括号匹配问题

括号匹配问题：

给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。

例如：
()()[]{} 　　 匹配
([{()}]) 　　 匹配
[](               不匹配
[(])              不匹配

利用堆栈的思路：
建立一个堆栈，然后遍历字符串，如果是‘(‘,‘{‘.‘[‘，则入栈，否则判断当前字符串和栈顶元素是否是一对括号；要注意的是，需要提前判断栈是否为空，为空的时候取top是违法的的，所以只要为空就入栈，然后执行下一次循环，而且，只要循环过程中出现一次栈顶元素和当前元素不匹配的情况，就可以跳出循环返回false了。

int isBracket(char left,char right)
{
    if(left == ‘(‘ && right == ‘)‘)   return 1;
    if(left == ‘[‘ && right == ‘]‘)   return 1;
    if(left == ‘{‘ && right == ‘}‘)   return 1;
    
    return 0;
}
int isValidParentheses( char *str )
{
    int len;
    int i;
    T_Stack stack;
    int buf[100];
    int tmp;

    StackInit( &stack, buf, sizeof(buf)/sizeof(buf[0]));

    len = strlen( str );

    for( i = 0; i < len; i++ )
    {
        if( StackIsEmpty( &stack ) )
        {
            StackPush( &stack, str[i] );
            continue;
        }

        StackTop( &stack, &tmp );

        if( str[i] == ‘(‘ || str[i] == ‘[‘ || str[i] == ‘{‘)
        {
            StackPush( &stack, str[i]);
        }
        else if( isBracket( tmp, str[i] ) )
        {
            StackPop( &stack, &tmp );
        }
        else
        {
            return 0;
        }
    }

    return ( StackIsEmpty( &stack ) );
}

int main( void )
{
    char *str[] = {
        "()()[][]{}", "[(])", "[]( ", "([{()}])", "(([{()}]) "
    };
    int i;
    
    for( i = 0; i < sizeof(str)/sizeof(str[0]); i++ )
    {
        printf("%s\r\n", isValidParentheses(str[i]) ? "match" : "not match");
    }

    system("pause");

    return 0;
}

参考引用：

https://www.jianshu.com/p/be1dc368200d

https://www.cnblogs.com/hedeyong/p/7841548.html