match.cpp

读入圆括号和方括号的任意序列

#include <stdio.h> 
#include <stdlib.h>
#include <malloc.h>
#include <conio.h> 

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10 
typedef char SElemType; 
typedef int Status;
typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}Sqstack;

int InitStack(Sqstack &S){
	if(!(S.base=(SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType))))
		exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

int StackEmpty(Sqstack S){
	if(S.top==S.base)
		return TRUE;
	else
		return FALSE;
}

int StackLength(Sqstack S){
	return S.top-S.base;
}

int GetTop(Sqstack S,SElemType &e){
	if(S.top>S.base){
		e=*(S.top-1);
		return OK;
	}else 
		return ERROR;
}

int 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.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*(S.top)++=e;
	return OK;
}

int Pop(Sqstack &S,SElemType &e){
	if(S.top==S.base)
		return FALSE;
	e=*--S.top;
	return OK;
} 

void matching(){
	Sqstack S;
	InitStack(S);
	char *p,a[100],e;
	int state;
	gets(a);
	p=a;
	state=1;
	while(*p && state){
		if(!*p=='[' || !*p==']' || !*p=='(' ||! *p==']'){
			printf("输入不正确!");
			exit(ERROR);
		}
		switch (*p){ 
		case '(':
			Push(S,*p++);
			break;
        case '[':
			Push(S,*p++);
			break;
		case ']':{
			GetTop(S,e);
			if(!StackEmpty(S) && e=='['){ 
				Pop(S,e);
				p++;
			}else
				state=0;
			break;}
		case ')':{
			GetTop(S,e);
			if(!StackEmpty(S) && e=='('){ 
				Pop(S,e);
				p++;
			}else
				state=0;
			break;
        }
		}
	}
	if(StackEmpty(S) && state && a[0]!='[')
		printf("输入的括号匹配!\n");
	else
		printf("输入的括号匹配不合法!\n");
}


void main(){
	printf("******************************************\n");
    printf("         实验2-2  括号匹配的检验\n");
    printf("******************************************\n");
	printf("请输入一组符号(只能含有()和[]):\n");
	matching();
}