括号匹配检验

括号匹配检验 利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。 Inpu t 第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。 Ou tpu t 第一行：若输入表达式括号匹配，输出"matching"; 若不匹配，输出具体信息:"isn't matched pairs", 或"lack of left parenthesis"或"lack of right parenthesis" ty pedef char SElemTy pe; #inclu de"malloc.h" #inclu de"stdio.h" #inclu de"math.h" #inclu de"process.h" // ex it() #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 ty pedef int Statu s; // Statu s 是函数的类型,其值是函数结果状态代码，如OK 等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base 的值为 NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); S.top=S.base; if(!S.base) return ERROR; S.stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) {if(S.base==S.top) return TRUE; else return FALSE; } Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(SElemType)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize=S.stacksize+STACK_INIT_SIZE;} *S.top=e; S.top++; return OK; } Status Pop(SqStack &S,SElemType &e) { if(S.base==S.top) return ERROR; e=*--S.top; return OK; } void check() { // 对于输入的任意一个字符串，检验括号是否配对 SqStack s; SElemType ch[80],*p,e; if(InitStack(s)) // 初始化栈成功 { //printf("请输入表达式\n"); scanf("%s",ch); p=ch; while(*p) // 没到串尾 switch(*p) { case '(': case '[':Push(s,*p);p++; break; // 左括号入栈，且 p++ case ')': case ']':if(!StackEmpty(s)) // 栈不空 { Pop(s,e); // 弹出栈顶元素 if(*p==')'&&e!='('||*p==']'&&e!='[') // 弹 出的栈顶元素与*p 不配对 { printf("isn't matched pairs\n"); exit(ERROR); } else { p++; break; // 跳出switch 语句 } } else // 栈空 { printf("lack of left parenthesis\n"); exit(ERROR); } default: p++; // 其它字符不处理，指针向后移 } if(StackEmpty(s)) // 字符串结束时栈空 printf("matching\n"); else printf("lack of right parenthesis\n"); } } void main() { check(); }