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

shenwenjie 2020-03-20

括号匹配问题:

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

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

利用堆栈的思路:
建立一个堆栈,然后遍历字符串,如果是‘(‘,‘{‘.‘[‘,则入栈,否则判断当前字符串和栈顶元素是否是一对括号;要注意的是,需要提前判断栈是否为空,为空的时候取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

相关推荐