完整示例
See the Pen 括号匹配算法演示 by 戴兜 (@DaiDR) on CodePen.
花了大概一早上写了这个示例，没有使用任何第三方库，完成度也算是比较高，除本文所讲的括号匹配算法有效性判定算法以外，涉及不依赖覆盖层的canvas点击位置判定、canvas绘制文字间距自定义，蛮有意思。文章篇幅有限，感兴趣的朋友可以去gist了解下实现方式。
Ⅰ. 括号匹配算法
代码语言：javascript复制(1)(2)(3)(4)(5)观察上面这组括号，不难发现当 ) 的左侧不存在另一个 ) 时（即未发生嵌套时），最靠近它的 ( 便是和它所对应的括号。
由提供的右括号位置开始向左遍历字串，当找到第一个 ( 的时候，我们便可以断定这个 ( 就是我们要找的左括号，代码大概长下面这样子：
function findL(str, pos) {
let nPos = pos - 1; // 跳过当前位置
do {
if (str[nPos] == "(") {
return nPos; // 直接返回括号位置
} else {
nPos--; // 跳过普通字符，继续向前遍历
}
} while (nPos > 0);
return -1; // 未找到对应的左括号
}但在出现括号嵌套时，事情似乎变得复杂了起来—— ((1))((2))((3))
最先出现在 ) 左侧的 ( ，可能不再是与其对应的括号了。不过，最内层的那对括号（即示例中最靠近数字的那几对），似乎依然符合我们之前所找到的规律。
既然最内层的括号依然能够被匹配，似乎也不是无药可救。既然数字能够被跳过，内部嵌套的括号也应该可以被跳过才对。我们通过递归来匹配内部嵌套的括号并将其跳过。完整代码如下：
代码语言：javascript复制function findL(str, pos) {
let nPos = pos - 1; // 跳过当前位置
do {
if (str[nPos] == "(") {
return nPos; // 直接返回括号位置
} else if (str[nPos] == ")") {
nPos = findL(str, nPos) - 1; // 寻找并跳过子括号位置
} else {
nPos--; // 跳过普通字符，继续向前遍历
}
} while (nPos > 0);
return -1;
}当然，通过左括号来寻找所对应的右括号逻辑也是相似的，只不过改成了从左往右遍历。
代码语言：javascript复制function findR(str, pos) {
let nPos = pos 1; // 跳过当前位置
do {
if (str[nPos] == ")") {
return nPos; // 直接返回括号位置
} else if (str[nPos] == "(") {
nPos = findR(str, nPos) 1; // 寻找并跳过子括号位置
} else {
nPos ; // 跳过普通字符，继续向前遍历
}
} while (nPos < str.length);
return -1;
}Ⅱ. 有效性判定
我们没有办法保证每次匹配的字串都是有效的，像 )()((()()( 这种情况可能就会抛出错误。所以在匹配前对字符串进行简单的校验是必要的。
如何校验？逻辑相似，我们只需要校验每对括号是否都被匹配就行了。从左向右遍历字串，如果当前位置是 ( 时，将其压入数组。如果当前位置是 ) 时，判断数组中的最后一个成员是否为 ( ，如果是，则将数组中的最后一个 ( 移除，反之将 ) 也压入数组。现在结果就很明显了，如果数组中仍然有成员没被移除，说明字串中有括号不是成对出现的（即字串无效）。代码大概是下面这个样子：
function validateText(str) {
let stack = [];
let textLength = str.length; // 取出文本长度
for (let i = 0; i < textLength; i ) {
if (!!stack.length && (stack[stack.length - 1] == "(" && str[i] == ")")) {
stack.pop();
} else if (str[i] == "(" || str[i] == ")") {
stack.push(str[i]);
}
}
return !stack.length;
}– The End –
code{background: #f5f2f0;}
