顺序栈的应用二：括号匹配的检验

括号匹配

假设表达式中允许包含三种括号：圆括号( )、方括号[ ]和花括号{ }，其嵌套的顺序随意。
{ ( [ ] ( ) ) }或[ { ( [ ] [ ] ) } ]等为正确的格式，[ ( ] 、( [ ( ) ) 、( ( ) ]均为不正确的格式。
检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
例如考虑下列括号序列：

[	(	[	]	[	]	)	]
1	2	3	4	5	6	7	8

当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号‘[’只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号‘)'的出现...这个处理的过程与栈的特点相吻合。

由此，在算法中设置一个栈，每读入一个括号，若是右括号，则使置于栈顶的最急迫的期待得以消解，若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。

BracketMatching.c利用了前面的C封装的顺序栈对象 用线性表表示的顺序栈
实现了输入任意一串字符串，检测字符串中三种括号是否匹配的功能。

github源码

BracketMatching.c文件

#include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"

int bracketMatching(char *str){
    char elem;
    int result = 0;
    int bracket_contained = 0;
    LinearListStack *stack = InitLinearListStack();
    while(*str != '\0'){
        if(*str == '{' || *str == '[' || *str == '('){
            bracket_contained = 1;
            stack->push(stack,str);
        }else if(*str == '}'){
            bracket_contained = 1;
            if(stack->length(stack)){
                stack->getTop(stack,&elem);
                if(elem == '{'){
                    stack->pop(stack,&elem);
                }else if(elem == '('){
                    printf("Bracket matching failed : \')\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }else if(elem == '['){
                    printf("Bracket matching failed : \']\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }
            }else{
                printf("Bracket matching failed : \'{\' expected! \n");
                DestroyLinearListStack(stack);
                return 0;
            }
        }else if(*str == ']'){
            bracket_contained = 1;
            if(stack->length(stack)){
                stack->getTop(stack,&elem);
                if(elem == '['){
                    stack->pop(stack,&elem);
                }else if(elem == '{'){
                    printf("Bracket matching failed : \'}\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }else if(elem == '('){
                    printf("Bracket matching failed : \')\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }
            }else{
                printf("Bracket matching failed : \'[\' expected! \n");
                DestroyLinearListStack(stack);
                return 0;
            }
        }else if(*str == ')'){
            bracket_contained = 1;
            if(stack->length(stack)){
                stack->getTop(stack,&elem);
                if(elem == '('){
                    stack->pop(stack,&elem);
                }else if(elem == '['){
                    printf("Bracket matching failed : \']\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }else if(elem == '{'){
                    printf("Bracket matching failed : \'}\' expected! \n");
                    DestroyLinearListStack(stack);
                    return 0;
                }
            }else{
                printf("Bracket matching failed : \'(\' expected! \n");
                DestroyLinearListStack(stack);
                return 0;
            }
        }
        str++;
    }
    if(bracket_contained){
        if(stack->length(stack) == 0){
            printf("Bracket matching successed\n");
            result = 1; 
        }else{
            stack->getTop(stack,&elem);
            switch(elem){
                case '{':
                    printf("Bracket matching failed : \'}\' expected! \n");
                    break;
                case '[':
                    printf("Bracket matching failed : \']\' expected! \n");
                    break;
                case '(':
                    printf("Bracket matching failed : \')\' expected! \n");
                    break;
            }
            result = 0;
        }
    }else{
        printf("String doesn't contain bracket!\n");
        result = 0;
    }
    DestroyLinearListStack(stack);
    return result;
}

int main(void)
{
    int num;
    char str[100];
    printf("please enter a string!\n");
    gets(str);
    printf("\n");
    bracketMatching(str);
    return 0;
}

编译：

gcc LinearListStack.c LinearListStack.h BracketMatching.c -o BracketMatching

运行BracketMatching,显示：

please enter a string!

示例：

输入：
DestroyLinearListStack(stack);
Bracket matching successed
输入：
if(stack->length(stack) == 0){
Bracket matching failed : '}' expected!
输入：
if(stack->length(stack))
Bracket matching successed
输入：
([())
Bracket matching failed : ']' expected!
输入：
(()]
Bracket matching failed : ')' expected!
输入：
if(elem == '(')
Bracket matching failed : ')' expected!
输入：
[([][])]
Bracket matching successed