数据结构上机3栈-括号匹配-白红宇

数据结构上机3栈-括号匹配

阅读量：7130 次

发布时间：2019-06-28

本文共 2706 字，大约阅读时间需要 9 分钟。

#include 
     
      #include 
      
       #define OK              1#define OVERFLOW       -1#define ERROR           0#define STACK_INIT_SIZE 100#define STACKINCREMENT  10typedef char SElemType;typedef int Status;typedef struct{    SElemType  * base;    SElemType  * top;    int          stacksize;}SqStack;///初始化栈Status InitStack_Sq(SqStack * S){    S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));    if(!S)        exit(OVERFLOW);    S->top = S->base;    S->stacksize = STACK_INIT_SIZE;    return OK;}///栈是否为空Status EmptyStack(SqStack * S){    if(S->top == S->base)        return OK;}///栈置空Status ClearStack(SqStack * S){    S->top = S->base;    return OK;}///压栈Status Push(SqStack * S, SElemType e){    if(S->top - S->base >= S->stacksize){        S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));        if(!S->base)            exit(OVERFLOW);        S->top = S->top + S->stacksize;        S->stacksize += STACKINCREMENT;    }    *S->top++ = e;    return OK;}///出栈Status Pop(SqStack *S, SElemType * e){    if(S->top == S->base)        return ERROR;    *e = * --S->top;    return OK;}/************************************************************ *          匹配括号()[]                                     * * 1. 初始化栈->栈是否为空(不是空栈则置空)                      * * 2. 遍历字符串                                             * *     a.([压栈 b.)]匹配栈顶出栈 c.不匹配为多余 d.其他字符跳过   * * 3.匹配结束  输出栈中内容                                   * *                                                         * ************************************************************/void  brackets(char * ch){    SqStack S;    SElemType e, *p;    int i = 0, j=1;    if(!InitStack_Sq(&S))        puts("初始化失败\n");    if(EmptyStack(&S))        printf("\n匹配前:\n    栈为空\n");    else        ClearStack(&S);    printf("\n开始匹配:\n");    while(ch[i]){        if(ch[i]== '[' || ch[i] == '('){            Push(&S, ch[i++]);            continue;        }        p = S.top-1;        if(EmptyStack(&S)!=OK)            if(*p == ch[i]-2 || *p == ch[i]-1){                 Pop(&S, &e);                 printf("%3d 第%3d个字符 %c 与栈顶 %c 匹配\n", j++, ++i, ch[i], e);                continue;            }        if(ch[i] == ']' || ch[i] == ')'){            printf("%3d 第%3d个字符 %c 无匹配值\n", j++, ++i, ch[i]);            continue;        }        i++;    }    p = S.top;    if(EmptyStack(&S)!=OK){        printf("\n匹配后:\n    栈中还剩下:\n");        while (p--!=S.base)            printf("%c ", *p);    }    else        printf("\n匹配后:\n    栈为空,匹配成功");}int main(void){    char ch[50];    puts("请输入字符串: ");    gets(ch);    brackets(ch);    printf("\n");    return 0;}