PHP实现括号匹配检查

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

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

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

实现算法:
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%。

参考:
网络流传给广,定义两个括号数组的方式,也值得借鉴,点击查看

发表评论

电子邮件地址不会被公开。 必填项已用*标注