思考这样一个经典的问题，检查一个字符串中的括号(只有括号)是否匹配？

很多年前在面试的时候被问到这个问题，自己想到的是用正则来处理，具体实现的时候又无法兼容全部情况。

事后知道用栈就能很容易的处理。栈是一种特殊的线性表，只能在一端进行插入和删除操作，具有后进先出的特点。

实现算法：
0、遍历字符串，判断括号类型
1、如果是左括号，添加到数组中
2、如果是右括号，从数组中取出最后一个元素，没有元素或不匹配验证失败；匹配这删除元素，继续
3、遍历完后，检查数组是否为空，为空则验证成功，否则验证失败。

一、粗暴的实现, 仅检查小括号

$str = '(())';
function validate($str)
{	
	$stack = [];
	$len = strlen($str);
	for ($i = 0; $i < $len; ++$i) {
		if ($str[$i] == '(') {
			$stack[] = $str[$i];
		} elseif ($str[$i] == ')') {
			$last_str = array_pop($stack);
			if ($last_str == '(') {
				continue;
			} else {
				return false;
			}
		}
	}

	if (empty($stack)) {
		return true;
	}

	return false;
}

$str = '(())';
var_dump(validate($str));

二、优化后的实现

function isValid($str)
{
	$map = [
		')' => '(',
		']' => '[',
		'}' => '{',	
	];

	$stack = [];
	$elements = str_split($str);
	foreach ($elements as $element) {
		if (in_array($element, $map)) {
			// array_push效率没有[]高
			// array_push($stack, $element);
			$stack[] = $element;
		} else {
			// 如果栈为空，或者栈顶的元素不匹配右括号，则验证失败
			if (empty($stack) OR $map[$element] != array_pop($stack)) {
				return false;
			}
		}
	}

	return empty($stack);
}

$str = '(())[()]{';
var_dump(isValid($str));

除了用栈的思路，还有其他的方法，当然栈是最优的。如果能想到用栈处理，问题就完成了60%。

参考：
网络流传很广，定义两个括号数组的方式，也值得借鉴，点击查看。