栈的应用--括号匹配问题

算法思路：

1、首先从左往右扫描各个括号

2、如果出现左半括号，就将其压入栈中，

3、如果扫描到右半括号，就将其和栈顶元素进行对比，

        3.1、如果栈空（没有栈顶元素），则匹配失败，

        3.2、如果栈不为空，弹出栈顶元素，将栈顶元素和该右半括号进行比较，小括号匹配小括号，如果匹配失败，结束

4、全部匹配完以后，判断栈是否为空，如果栈不为空，说明还有未匹配的左半括号，如果栈为空，说明括号匹配成功

代码实现

#include <stdio.h>

// 括号匹配问题 

#define  MaxSize 10

typedef struct{
	char data[MaxSize];	// 静态数组存放栈中元素 
	int top;			// 栈顶指针  指向数组下标，从0开始 
}SqStack;


// 1、初始化
bool InitStack(SqStack &S){
	S.top = -1;		// 初始化栈顶指针 
	return true;
} 

// 2、判断栈空
bool IsEmpty(SqStack S){
	if(S.top == -1){	// 栈空 
		return true;
	}else{
		return false;
	}
} 

// 3、入栈
bool PushELem(SqStack &S,char e){
	if(S.top == MaxSize - 1){	// 栈满，不能插入新元素 
		return false; 
	}
	S.top = S.top + 1;		// 先将栈顶指针 +1
	S.data[S.top] = e;		// 新元素入栈
	
	// 两行合并
	// S.data[++S.top] = e  指针先加 1 ，再入栈    
	return true;
} 

// 4、出栈
bool PopElem(SqStack &S,char &e){	// 元素出栈，并将出栈元素返回 
	if(S.top == -1){	// 栈空 
		return false;
	} 
	e = S.data[S.top];	// 栈顶元素出栈 
	S.top = S.top - 1;
	//	e = S.data[S.top--]; 先出栈，指针 -1 
	return true;
}  

// 5、读取栈顶元素
bool Top(SqStack S,char &e){
	if(S.top == -1){	// 栈空 
		return false;
	}
	e = S.data[S.top];
	return true;
} 

// 括好匹配问题
bool Cheak(char str[],int length){		// length 表示数组长度 
	SqStack S;
	InitStack(S);
	for(int i = 0;i<length ;i++){
		if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
			PushELem(S,str[i]);		// 扫描到左括号 ，入栈 
		}else{
			
			if(IsEmpty(S)){			// 扫描到右括号，但是栈为空 
				return false;		// 匹配失败 
			}
			
			char topELem;
			PopElem(S,topELem);		// 栈顶元素出栈，出栈元素保存在 topELem 中 
			if(str[i] == ')' && topELem != '(') {
				return false;
			}
			if(str[i] == ']' && topELem != '[') {
				return false;
			}
			if(str[i] == '}' && topELem != '{') {
				return false;
			}
		} 
	}
	
	return IsEmpty(S);		// 检查完全部元素后， 栈空说名匹配成功 
} 


int main()
{ 
	SqStack S;
	
	char str[] = {'{','[',']','}','{','['};
	
	int length = sizeof(str)/sizeof(str[0]);
	
	for(int i = 0;i<length;i++){
		printf("%c ",str[i]);
	}
	printf("\n\n");
	
	if(Cheak(str,length)){
		printf("括号匹配成功！"); 
	}else{
		printf("括号匹配失败！"); 
	}
//	printf("%d",Cheak(str,length));
	
	return 0;
 } 

测试

{ [ ] } { [

括号匹配失败！
--------------------------------
Process exited after 0.01276 seconds with return value 0
请按任意键继续. . .

{ [ ] } { }

括号匹配成功！
--------------------------------
Process exited after 0.01009 seconds with return value 0
请按任意键继续. . .