数据结构括号匹配算法实现
时间: 2023-11-26 16:49:08 浏览: 42
以下是基于栈的括号匹配算法的实现过程:
1. 定义一个栈,用于存储左括号。
2. 遍历字符串中的每个字符,如果该字符是左括号,则将其压入栈中。
3. 如果该字符是右括号,则检查栈是否为空。如果为空,则说明没有与之匹配的左括号,返回False。如果栈不为空,则弹出栈顶元素,检查其是否与当前右括号匹配。如果不匹配,则返回False。
4. 如果遍历完字符串后,栈为空,则说明所有括号都匹配,返回True。否则返回False。
以下是PHP代码实现:
```php
function isValid($s) {
$stack = array();
$map = array(
')' => '(',
']' => '[',
'>' => '<'
);
for ($i = 0; $i < strlen($s); $i++) {
$char = $s[$i];
if (in_array($char, array('(', '[', '<'))) {
array_push($stack, $char);
} elseif (in_array($char, array(')', ']', '>'))) {
if (empty($stack)) {
return false;
}
$top = array_pop($stack);
if ($top != $map[$char]) {
return false;
}
}
}
return empty($stack);
}
```