栈的简单应用-括号匹配

　　假设表达式中运行包含两种括号：圆括号和方括号，其嵌套顺序随意，即

([]) 或 [([][])]等均为正确的格式。[(]) 或 ([()) 或 (())]均为不正确的格式。检验括号

匹配的方法可以用“期待的急迫程度”这个概念来描述

　　分析可能出现不匹配的情况：

　　（1）到来的右括弧不是所“期待”的；

　　（2）到来的是“不速之客”(右括弧多了)；

　　（3）直到结束也没有到来所“期待”的(左括弧多了)。

　　括号匹配的检验逻辑如下：

　　（1）凡是出现左括弧，则进栈。

　　（2）凡是出现右括弧，首先检查栈是否为空；

　　　　若栈空，则表明“右括弧”多了；

　　　　否则和栈顶元素比较：

　　　　若相匹配，则“左括弧出栈”；

　　　　否则不匹配。

　　（3）表达式检验结束时：

　　　　若栈空，则匹配正确；

　　　　否则表明“左括弧”多了。

　　sqstack.h:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//储存空间初始分配量
#define STACKINCREMENT  10//存储空间分配增量
#define OK 1
#define ERROR 0
typedef char StackType; //栈元素类型

typedef struct {
    StackType *base;   //在构造之前和销毁之后，base的值为NULL
    StackType *top;    //栈顶指针
    int stacksize;     //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈

//栈的初始化
int InitStack(SqStack *p) {


    p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
    if (p->base == NULL)  return ERROR;  //内存分配失败
    p->top = p->base;     //栈顶与栈底相同表示一个空栈
    p->stacksize = STACK_INIT_SIZE;
    return OK;

}
//判断栈是否为空
int EmptyStack(SqStack *p) {
    //若为空栈 则返回OK，否则返回ERROR
    if (p->top == p->base) return OK;
    else return ERROR;
}
//顺序栈的压入
int Push(SqStack *p, StackType e) {
    //插入元素e为新的栈顶元素
    if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间
    {
        p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType));
        if (p->base == NULL)   return ERROR;// 储存空间分配失败
        p->top = p->base + p->stacksize;    //可能有人觉得这句有点多余(我当时也是这么想的 后面有解释)
        p->stacksize += STACKINCREMENT;
    }
    *(p->top) = e;
    (p->top)++;
    return OK;
}
// 顺序栈的弹出     
int Pop(SqStack *p, StackType *e) {
    //若栈不空，则删除p的栈顶元素，用e返回其值
    if (p->top == p->base) return ERROR;
    --(p->top);
    *e = *(p->top);
    return OK;


}
//顺序栈的销毁
int DestroyStack(SqStack *p) {
    //释放栈底空间并置空
    free(p->base);
    p->base = NULL;
    p->top = NULL;
    p->stacksize = 0;

    return OK;
}

　　具体代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 #include "sqstack.h" //引入顺序栈储存结构及其基本操作
 5 #define OK 1
 6 #define ERROR 0
 7 void check(){
 8     //对于输入的任意一个字符串判断其括号是否匹配
 9 
10     SqStack *s=(SqStack*)malloc(sizeof(SqStack));
11     
12     StackType str[100],*p=NULL,*e;
13     e = (StackType*)malloc(sizeof(StackType));
14     if (InitStack(s) == OK) {
15         printf("请输入表达式
");
16         gets(str);
17         p = str;
18         while (*p)  //没到串尾
19             switch (*p)
20             {
21             case'(':
22             case'[':
23                 Push(s, *p++); break;//左括号入栈 且p++
24             case')':
25             case']':
26                 if (EmptyStack(s) != OK) 
27                 {//栈不为空
28                     Pop(s, e); //弹出栈顶元素
29                     if(*p==')'&&*e!='('||*p=='['&&*e!=']')
30                         //弹出的栈顶元素与*p不匹配
31                     {
32                         printf("左右括号不匹配
");
33                         return; 
34                     }
35                     else
36                     {
37                         p++; 
38                         break;
39                     }
40 
41 
42                 }
43                 else //栈空
44                 {
45                     printf("缺乏左括号
");
46                     return;
47                 }
48             default: p++;//其他字符不处理，指针后移
49         }
50         if (EmptyStack(s) == OK) //字符串结束时栈空
51             printf("括号匹配
");
52         else
53             printf("缺乏右括号
");
54         
55 
56 
57 
58     }
59 
60 
61 
62 
63 }
64 
65 int main() {
66     check();
67     return 0;
68 
69 }