完整示例

See the Pen 括号匹配算法演示 by 戴兜 (@DaiDR) on CodePen.

花了大概一早上写了这个示例,没有使用任何第三方库,完成度也算是比较高,除本文所讲的括号匹配算法有效性判定算法以外,涉及不依赖覆盖层的canvas点击位置判定、canvas绘制文字间距自定义,蛮有意思。文章篇幅有限,感兴趣的朋友可以去gist了解下实现方式。

Ⅰ. 括号匹配算法

(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))

最先出现在 ) 左侧的 ( ,可能不再是与其对应的括号了。不过,最内层的那对括号(即示例中最靠近数字的那几对),似乎依然符合我们之前所找到的规律。

既然最内层的括号依然能够被匹配,似乎也不是无药可救。既然数字能够被跳过,内部嵌套的括号也应该可以被跳过才对。我们通过递归来匹配内部嵌套的括号并将其跳过。完整代码如下:

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;
}

当然,通过左括号来寻找所对应的右括号逻辑也是相似的,只不过改成了从左往右遍历。

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 -


在迷失中寻找自我