「栈」的应用系列之「括号匹配」

人非圣贤，孰能无过。即使是程序员大牛，在写程序时也难免会遇到编译器报错的情况。其中相信大家在写程序的时候都遇到过，那就是括号不匹配，特别是当一条表达式比较长时，各种括号互相嵌套，稍不留神就会出错。那么大家有没有想过，编译器是怎么知道我们写的程序括号不匹配的？答案其实就是栈。对于栈不熟悉的小伙伴可以参考我的这篇文章：栈

假设字符序列名为C，则利用栈来判别括号是否匹配的过程如下：

自左向右地逐个考查 C 中每个字符，如果遇到左括号（ ” ( “ 、 ” [ “ 、 ” { “ 中的任意一个），则将该括号入栈，如果遇到右括号（ ” ) “ 、 ” ] “ 、 ” } “ 中的任意一个），则将其与栈顶的括号比对，如果能正好凑成一对括号，则将栈顶的括号出栈，继续考查 C 中的下一个字符。如果不能正好凑成一对括号，则该 C 中的括号一定是不匹配的。如果 C 中所有字符都考察完了，而栈不为空，C 中的括号也是不匹配的。

以下面这两个括号序列为例，我们来看看具体的匹配过程。

序列一：{ ( ) [ ( { } ) ] } //匹配
序列二：{ ( ) [ ] ( { } ) ] } //失配

下面是两个括号序列的匹配过程：

C++ 代码实现如下：

#include "Stack.h"
/*检查表达式exp[low, high]中的括号是否匹配*/
bool paren(const char exp[], int low, int high) {
	Stack<char> S;
	while (low <= high) { //自左向右逐一检查各字符
		switch (exp[low]) {
			case '(': case '[':	case '{':  //当遇到左括号时
                 S.push(exp[low]); break; //将字符入栈
			case ')': //当遇到右括号时，判断栈是否为空，若不为空，则判断是否与栈顶符号相匹配
				if ((S.empty()) || ('(' != S.pop())) return false;
				break;
			case ']':
				if ((S.empty()) || ('[' != S.pop())) return false;
				break;
			case '}':
				if ((S.empty()) || ('{' != S.pop())) return false;
				break;
			default: break; //非括号字符一律忽略
		}
		low++;
	}
	return S.empty();
}

本文代码以及所用头文件 Stack.h 均已上传至 GitHub ，点击这里即可获得。

欢迎关注我的微信公众号，扫描下方二维码或微信搜索：AProgrammer，就可以找到我，我会持续为你分享 IT 技术。