括弧匹配，用栈写（顺序栈，链栈都可以）vc++6.0的调试下

Question

对输入的一组字符串进行检测，当输入的字符串中括号（包括“{}”，“[]”，“( )”）匹配时输出匹配，否则输出不匹配。

Answer 1

/*  括号（()、[]和{}）匹配的检验 */
#include <stdio.h>
#include <stdlib.h>
typedef char SElemType;
typedef int Status;
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACK_INCREMENT 2 /* 存储空间分配增量 */
#define    OK          1
#define    ERROR       0
#define    TRUE        1
#define    FALSE       0
#define    OVERFLOW    -2
typedef struct SqStack
{
    SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
    SElemType *top; /* 栈顶指针 */
    int stacksize; /* 当前已分配的存储空间，以元素为单位 */
} SqStack; /* 顺序栈 */
void InitStack(SqStack *S)
{
    /* 构造一个空栈S */
    (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!(*S).base)
        exit(OVERFLOW); /* 存储分配失败 */
    (*S).top=(*S).base;
    (*S).stacksize=STACK_INIT_SIZE;
}
void DestroyStack(SqStack *S)
{
    /* 销毁栈S，S不再存在 */
    free((*S).base);
    (*S).base=NULL;
    (*S).top=NULL;
    (*S).stacksize=0;
}
void ClearStack(SqStack *S)
{
    /* 把S置为空栈 */
    (*S).top=(*S).base;
}
Status StackEmpty(SqStack S)
{
    /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
    if(S.top==S.base)
        return TRUE;
    else
        return FALSE;
}
int StackLength(SqStack S)
{
    /* 返回S的元素个数，即栈的长度 */
    return S.top-S.base;
}
Status GetTop(SqStack S,SElemType *e)
{
    /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
    if(S.top>S.base)
    {
        *e=*(S.top-1);
        return OK;
    }
    else
        return ERROR;
}
void Push(SqStack *S,SElemType e)
{
    /* 插入元素e为新的栈顶元素 */
    if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
    {
        (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACK_INCREMENT)*sizeof(SElemType));
        if(!(*S).base)
            exit(OVERFLOW); /* 存储分配失败 */
        (*S).top=(*S).base+(*S).stacksize;
        (*S).stacksize+=STACK_INCREMENT;
    }
    *((*S).top)++=e;
}
Status Pop(SqStack *S,SElemType *e)
{
    /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
    if((*S).top==(*S).base)
        return ERROR;
    *e=*--(*S).top;
    return OK;
}
void StackTraverse(SqStack S,void(*visit)(SElemType))
{
    /* 从栈底到栈顶依次对栈中每个元素调用函数visit() */
    while(S.top>S.base)
        visit(*S.base++);
    printf("\n");
}
void check()
{
    /* 对于输入的任意一个字符串，检验括号是否配对 */
    SqStack s;
    SElemType ch[80],*p,e;
    InitStack(&s); /* 初始化栈成功 */
    printf("请输入带括号（()、[]和{}）的表达式\n");
    gets(ch);
    p=ch; /* p指向字符串的首字符 */
    while(*p) /* 没到串尾 */
        switch(*p)
        {
        case '(':
        case '[':
        case '{':
            Push(&s,*p++); /* 左括号入栈，且p++ */
            break;
        case ')':
        case ']':
        case '}':
            if(!StackEmpty(s)) /* 栈不空 */
            {
                Pop(&s,&e); /* 弹出栈顶元素 */
                if(!((e=='('&&*p==')')||(e=='['&&*p==']')||(e=='{'&&*p=='}')))
                {
                    /* 出现3种匹配情况之外的情况 */
                    printf("左右括号不配对\n");
                    exit(ERROR);
                }
            }
            else /* 栈空 */
            {
                printf("缺乏左括号\n");
                exit(ERROR);
            }
        default:
            p++; /* 其它字符不处理，指针向后移 */
        }
    if(StackEmpty(s)) /* 字符串结束时栈空 */
        printf("括号匹配\n");
    else
        printf("缺乏右括号\n");
}
int main()
{
    check();
    return 0;
}

运行结果如下：