JavaScript实现括号匹配检查：一次掌握栈操作
在许多编程场景中，我们都需要验证字符串中的括号是否正确匹配。例如，{a(b)c} 是有效的，而 {a(b 或 {a(b)c) 则是无效的。这一问题的核心解法就是利用栈（Stack）这种数据结构。
栈的工作原理
- 栈是一种顺序存储的线性结构，遵循先进后出（FILO）原则
- 在JavaScript中，常用数组模拟栈操作，主要使用
push()和pop()方法 - 栈可以作为自定义的业务逻辑实现，不局限于语言本身
匹配算法解析
- 遍历字符串的每个字符
- 遇到左括号
{ ( [时，将其压入栈中 - 遇到右括号
} ) ]时，弹出栈顶的左括号并检查是否配对 - 若配对则继续，若不配对直接返回false
- 遍历结束后，检查栈是否为空；为空则表示全部匹配，否则表示有未闭合括号
完整代码实现
/**
* 验证左右括号是否成对
*/
function isPaired(left: string, right: string): boolean {
const pairs: Record<string, string> = {
'{': '}',
'(': ')',
'[': ']'
};
return pairs[left] === right;
}
/**
* 主函数：检查字符串中的括号是否平衡
*/
function validateBrackets(input: string): boolean {
if (input.length === 0) return true;
const stack: string[] = [];
const openers = '{([';
const closers = '}])';
for (const char of input) {
// 左括号入栈
if (openers.includes(char)) {
stack.push(char);
}
// 右括号处理
else if (closers.includes(char)) {
const top = stack.pop();
if (!top || !isPaired(top, char)) {
return false;
}
}
// 其他字符忽略
}
// 栈中是否还有未匹配的左括号
return stack.length === 0;
}
复杂度分析
- 时间复杂度：O(n)，其中n为字符串长度，每个字符只处理一次
- 空间复杂度：O(n)，最坏情况下所有字符都是左括号，栈的大小等于n
单元测试
import { validateBrackets } from './bracketValidator';
describe('括号匹配检测', () => {
test('完全匹配', () => {
expect(validateBrackets('{a(b[c]d)e}f')).toBe(true);
});
test('多余右括号', () => {
expect(validateBrackets('a(b[c]d)e}f')).toBe(false);
});
test('括号顺序错误', () => {
expect(validateBrackets('{a(b[c]d}e)f')).toBe(false);
});
test('空字符串', () => {
expect(validateBrackets('')).toBe(true);
});
test('只有左括号', () => {
expect(validateBrackets('{{[(')).toBe(false);
});
test('包含其他字符', () => {
expect(validateBrackets('function() { return [1,2,3]; }')).toBe(true);
});
});
通过这个简单的栈应用场景，我们可以深入理解栈的先进后出特性，并将其灵活运用到实际开发中。
