데이터 구조 - 스 택 괄호 일치 에서 의 응용

괄호 검사 가 일치 하 는 것 은 실질 적 으로 여러 종류의 괄호 를 정확하게 맞 추 는 검사 (((), [], {} 포함) 즉 ([]) 또는 [()] 를 정확 한 표현 식 으로 하 는 것 입 니 다. 교차 가 나타 나 면 일치 하 는 데 실 패 했 습 니 다. 예 를 들 어 [(] 또는 ()))올 바 르 지 않 은 형식 입 니 다. 이 프로그램 은 스 택 의 사상 도 사 용 했 습 니 다. 왼쪽 괄호 가 있 으 면 스 택 에 들 어 갑 니 다. 오른쪽 괄호 가 있 으 면 현재 스 택 상단 요소 와 일치 하 는 지 여 부 를 봅 니 다. 스 택 에서 나 오 면 현재 표현 식 괄호 가 일치 하지 않 습 니 다.
프로그램 사상: 1. 빈 스 택 을 초기 에 설정 하고 괄호 를 순서대로 읽 습 니 다. 2. 오른쪽 괄호 가 있 으 면 스 택 꼭대기 에 있 는 요 소 를 스 택 에서 나 오 게 합 니 다. 괄호 서열 이 일치 하지 않 으 면 프로그램 을 종료 합 니 다. 3. 왼쪽 괄호 가 있 으 면 요 소 를 스 택 에 누 르 고 알고리즘 이 끝 날 때 스 택 이 비어 있 습 니 다. 그렇지 않 으 면 괄호 서열 이 일치 하지 않 습 니 다.
 
다음은 예제 코드 입 니 다.

//           

#include "stdafx.h"
#include "string.h"

#define ElementType char
#define MaxSize 10
//     
typedef struct {
	ElementType data[MaxSize];//   
	int top;//    
	int size;//     
}SqStack;

/*
    
*/
void InitStack(SqStack &s) {
	s.top = -1;
	s.size = 0;
}

/*
       
*/
bool StackEmpty(SqStack s) {
	if (s.size == 0) {
		return true;
	}
	return false;
}
/*
  
*/
bool PushStack(SqStack &s,ElementType e) {
	//if(s.top==MaxSize-1)
	if (s.size == MaxSize) {
		//  
		return false;
	}
	s.top++;
	s.data[s.top] == e;
	s.size++;
	return true;
}
/*
  
*/
ElementType PopStack(SqStack &s) {
	//if(s.top==-1)
	if (s.size==0) {
		//  
		return NULL;
	}
	ElementType e = s.data[s.top];
	s.top--;
	s.size--;
	return e;
}
/*
        
*/
bool CheckMatch(char *str) {
	SqStack stack;
	InitStack(stack);
	int len = strlen(str);
	for (int i = 0; i < len; i++)
	{
		char x = str[i];
		ElementType e;
		switch (x) {
		case '(':
			PushStack(stack, x);
			break;
		case '[':
			PushStack(stack, x);
			break;
		case '{':
			PushStack(stack, x);
			break;
		case ')':
			e = PopStack(stack);
			if (e != '(') {
				return false;
			}
			break;
		case ']':
			e = PopStack(stack);
			if (e != '[') {
				return false;
			}
			break;
		case '}':
			e = PopStack(stack);
			if (e != '{') {
				return false;
			}
			break;
		}
	}
	bool b = StackEmpty(stack);
	if (b) {
		return true;
	}
	return false;
}

void main() {
	char str[] = "[({})]";
	bool b = CheckMatch(str);
	if (b) {
		printf_s("    ");
	}
	else
	{
		printf_s("    ");
	}
}