数据结构6.1-栈的应用之括号匹配

括号匹配是数据结构中比较常见的应用之一，其算法思路如下：

①顺序遍历给定test的每一个字符

②对于除了括号之外的无关字符直接跳过

③遇到开括号就压入栈

④遇到闭括号就弹出当时的栈顶元素与之匹配

⑤如果匹配成功则继续，如果不匹配则以失败结束

由于括号匹配大部分代码与栈的基础操作相同，下面只展示核心代码：

bool bracketMatching(char* paraString, int paraLength) {
    int i;

	// 第一步：通过压入‘#’到栈底来初始化栈
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');   //压入‘#’到栈底的目的之一是为了避免第一个字符为‘（、{、[’的情况
	char tempChar, tempPopedChar;

	// 第二步：字符遍历匹配
	for (i = 0; i < paraLength; i++) {  //遍历当前元素
		tempChar = paraString[i];
		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);  //左括号入栈
			break;
		case ')':
			tempPopedChar = pop(tempStack); 
			if (tempPopedChar != '(') {
				return false;
			} 
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			} 
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			} 
			break;
            //右括号出栈            
		default:
			
			break;
		}
	} 
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {     //遍历结束后如果栈还有字符则括号不匹配
		return false;
	}

	return true;
}

//测试
void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";  
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}

#include 
#include 
#include 

#define STACK_MAX_SIZE 10  //固定栈的长度 
 
 
typedef struct CharStack {
    int top;
 
    int data[STACK_MAX_SIZE]; 
} *CharStackPtr;
 
//输出栈的元素 
void outputStack(CharStackPtr paraStack) {
	int i; 
    for (i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }
    printf("rn");
}
 
//栈的初始化 
CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStackPtr));  //申请内存 
	resultPtr->top = -1;
 
	return resultPtr;
}
 
//压栈 
void push(CharStackPtr paraStackPtr, int paraValue) {
    // 第一步：检查当前元素空间 
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("栈空间已满，不能压入当前元素rn");
        return;
    }
 
    // 第二步：更新当前元素 
	paraStackPtr->top ++;
 
	// 第三步：压入当前元素 
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}
 
//弹栈 
char pop(CharStackPtr paraStackPtr) {
    // 第一步：检查空间 
    if (paraStackPtr->top < 0) {
        printf("栈空间已满，不能弹出当前元素rn");
        return '';
    }
 
    // 第二步：更新元素 
	paraStackPtr->top --;
 
	// 第三步：弹入元素 
    return paraStackPtr->data[paraStackPtr->top + 1];
}
 
 bool bracketMatching(char* paraString, int paraLength) {
    int i;

	// 第一步：通过压入‘#’到栈底来初始化栈
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');   //压入‘#’到栈底的目的之一是为了避免第一个字符为‘（、{、[’的情况
	char tempChar, tempPopedChar;

	// 第二步：字符遍历匹配
	for (i = 0; i < paraLength; i++) {  //遍历当前元素
		tempChar = paraString[i];
		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);  //左括号入栈
			break;
		case ')':
			tempPopedChar = pop(tempStack); 
			if (tempPopedChar != '(') {
				return false;
			} 
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			} 
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			} 
			break;
            //右括号出栈            
		default:
			
			break;
		}
	} 
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {     //遍历结束后如果栈还有字符则括号不匹配
		return false;
	}

	return true;
}
 
 //测试
void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";  
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}
 
//弹压元素测试 
void pushPopTest() {
	int i;
	char ch;
    printf("---- 弹压测试开始 ----rn");
 
	// 初始化 
    CharStackPtr tempStack = charStackInit();
    printf("初始化过后，这个栈是：");
	outputStack(tempStack);
 
	// 压栈 
	for (ch = 'a'; ch < 'm'; ch ++) {
		printf("压入 %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
 
	// 弹栈 
	for (i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("弹入 %c.rn", ch);
		outputStack(tempStack);
	}
 
    printf("---- 弹压测试结束 ----rn");
}
 
 
void main() {
	//pushPopTest();
	bracketMatchingTest();
}