栈的应用：检查括号匹配性

题目背景

我们都知道，在编程语言中，我们常用多种类型的括号，( )圆括号、[ ]方括号、{ }花括号，当括号不匹配时，编译时会发生错误。那么编译器是如何检验括号匹配性的呢？

题目分析

下面列举了若干实例帮助理解匹配性的判断标准

Expression	Balanced？	Reason
{(a+b)+[a-b]}	Yes
)(	No	右括号必须在左括号右边
[ ( ] )	No	后出现的左括号要先完成匹配(Last Opened First Closed)
[ ( ) ( ) ]	Yes	任何右括号要对应它左侧距它最近的左括号

代码实现

代码

#include<iostream>
#include<stack>
using namespace std;
stack<char> S;//定义一个用于存放括号的栈
int match(char c){//设计一个match函数，如果右括号和位于栈顶的左括号相匹配返回1，否则返回0
	if((S.top()=='('&&c==')')||(S.top()=='['&&c==']')||(S.top()=='{'&&c=='}'))
	return 1;
	else
	return 0;
}
char a[20];
int main(){
	gets(a);
	char exp;//该变量用于存放当前的左括号
	int len = strlen(a);
	for(int i=0;i<len;i++){
		exp = a[i];
		if(exp=='('||exp=='['||exp=='{')//当识别到左括号即进栈
			S.push(exp);
		else if(exp == ')'||exp == ']'||exp == '}'){//如果识别到右括号
			if(S.empty()||match(exp)==0){//如果栈内是空的（说明右括号前没有左括号）；或者括号不匹配
				printf("No");
				return 0;
			}
			else//如果匹配，则让匹配完成的左括号出栈
			S.pop();
		}
	}
	if(S.empty()){//完成遍历后，若栈中剩余括号，证明括号不匹配；若空栈，证明匹配
		printf("Yes");
		return 0;
	}
	else{
		printf("No");
		return 0;
	}
}

输入/出结果

example 1:

{(a+b)+[a-b]}
Yes

example 2:

)(
No

example 3:

[ ( ] )
No

example 4:

[ ( ) ( ) ]
Yes