창고 의 응용: 괄호 짝 짓 기

괄호 짝 짓 기 는 창고 안의 전형 적 인 문제 로 내 가 만난 횟수 도 한 수 일 것 이다.대학원 진학 을 틈 타 데이터 구 조 를 복습 하 러 또 한 번 왔 다.
괄호 짝 짓 기 는 보통 값 [] (), {}, [() {}], [({})] 과 같은 것 은 합 법 적 이 며, [] [, [], [], [(]) 와 같은 것 은 불법 입 니 다. 해결 의 방향 은 왼쪽 에서 오른쪽으로 순서대로 창고 에 들 어 가 는 것 입 니 다. 괄호 를 만나면 창고 의 괄호 와 일치 합 니 다. 일치 하지 않 거나 창고 의 꼭대기 가 비어 있 으 면 이 괄호 의 조합 서열 은 일치 하지 않 습 니 다.
스 택 은 스 택 을 배열 로 모 의 할 수도 있 고 C + STL 에 포 장 된 것 도 사용 할 수 있 으 며 스 택 을 스스로 정의 할 수도 있 습 니 다. 시험 과 면접 에서 스 택 을 실현 하 는 것 을 좋아 하기 때문에 저 는 앞에서 배 운 대로 순서 스 택 을 만들어 이 문 제 를 해결 합 니 다.
code:

#include 
#include 
#include 

#define MaxSize 100

typedef struct{
	char data[MaxSize];
	int top; //      
}SqStack;

//     
void StackInit(SqStack &S)
{
	S.top = 0;
}
//    
bool StackPush(SqStack &S, char e)
{
	if(S.top == MaxSize){
		return false;
	}
	S.data[S.top++] = e;
//	printf("S.data[S.top-1] = %c
", S.data[S.top-1]);
	return true;
}
//    
bool StackPop(SqStack &S)
{
	if(S.top == 0){
		return false;
	}
	S.top--;
	return true;
}
//       
char GetTop(SqStack S) 
{
	if(S.top == 0){
		exit(1);
	} 
	return S.data[S.top-1];
}
//    
bool StackIsEmpty(SqStack S)
{
	return (S.top == 0 ? true : false); 
}
//          
bool check(SqStack S, char e)
{
	char stop = GetTop(S); //        
	bool flag = false;
	//        
	if(stop == '[' && e == ']'){
		flag = true;
	}
	else if(stop == '(' && e == ')'){
		flag = true;
	}
	else if(stop == '{' && e == '}'){
		flag = true;
	}
	return flag;
}

int main() 
{
	SqStack S;
	StackInit(S);
	char str[MaxSize];
	scanf("%s", str);
	printf("str = %s
", str);
	int len = strlen(str);
	for(int i = 0; i < len; i++){
//		printf("str[%d] = %c
", i, str[i]);
		if(StackIsEmpty(S)){ //         
			StackPush(S, str[i]);
			
		}
		else if(check(S, str[i])){ //               
			StackPop(S);
			
		}
		else{
			StackPush(S, str[i]); //      
		}
	} 
	if(StackIsEmpty(S)){
		printf("Yes
");
	}
	else{
		printf("No
");
	}
	
	return 0;
}