用栈实现括号匹配

用栈实现括号匹配 

最近在复习数据结构，有关栈的一个问题：括号匹配。

问题描述：输入一串括号，然后判断左右括号是不是匹配的。

实验程序：

/*brackets_match.c*/

#include <stdio.h>

#define M 100

typedef struct Stack {
    char element[M];
    int top;
}Stack;

void InitStack(Stack *s)
{
    s->top = -1;
}

int PushStack(Stack *s, char ch)
{
    if(s->top == M-1) {
        return 0;
    }
    s->top++;
    s->element[s->top] = ch;
    return 1;
}

int PopStack(Stack *s, char *ch)
{
    if(s->top == -1) {
        return 0;
    }
    *ch = s->element[s->top];
    s->top--;
    return 1;
}

int GetTop(Stack *s, char *ch)
{
    if(s->top == -1) {
        return 0;
    }
    *ch = s->element[s->top];
    return 1;
}

int IsEmpty(Stack *s)
{
    if(s->top == -1) {
        return 1;
    } else {
        return 0;
    }
}

int MatchBracket(char ch1, char ch2)
{
    if(ch1 == '(' && ch2 == ')') {
        return 1;
    }
    if(ch1 == '[' && ch2 == ']') {
        return 1;
    }
    if(ch1 == '{' && ch2 == '}') {
        return 1;
    }
    return 0;
}

int main()
{
    Stack s;
    char str[M] = {0}, ch;
    int i;

    InitStack(&s);
    fprintf(stdout, "Input brackets:");
    fscanf(stdin, "%s", str);
    for(i = 0; str[i] != 0; i++) {
        switch(str[i]) {
            case '(':
            case '[':
            case '{':
                PushStack(&s, str[i]);
                break;
            case ')':
            case ']':
            case '}':
                if(IsEmpty(&s)) {
                    printf("right bracket spilth.\n");
                    return 0;
                } else {
                    GetTop(&s, &ch);
                    if(MatchBracket(ch , str[i])) {
                        PopStack(&s, &ch);
                    } else{
                        printf("left and right brackets are different.\n");
                        return 0;
                    }
                }
        }
    }
    if(IsEmpty(&s)) {
        printf("left and right brackets are matched.\n");
    } else {
        printf("left bracket spilth..\n");
    }
    return 0;
}

实验结果：

^_^[sunny@sunny-laptop ~/DS]10$ gcc brackets_match.c
^_^[sunny@sunny-laptop ~/DS]11$ ./a.out
Input brackets:[]
left and right brackets are matched.
^_^[sunny@sunny-laptop ~/DS]12$ ./a.out
Input brackets:{}{}
left and right brackets are matched.
^_^[sunny@sunny-laptop ~/DS]13$ ./a.out
Input brackets:{{{{{}}}}}}()
right bracket spilth.
^_^[sunny@sunny-laptop ~/DS]14$ ./a.out
Input brackets:{{{}}}()[]
left and right brackets are matched.