在 JavaScript 中查找括号分数

一、什么是括号分数

括号分数指的是一个字符串中括号的嵌套层数，如下面这个例子：

((1+2)*(3-4))/((5+6)*(7-8))

这个字符串中，最大的嵌套层数是2，也就是有两层括号。

二、查找括号分数的方法

1. 利用栈的思想

我们可以利用栈的思想来查找括号分数。

遍历字符串中的每个字符，当遇到左括号时，将该字符的序号压入栈中，当遇到右括号时，弹出栈顶元素，并计算当前括号中的嵌套层数。

function findBracketScore(str) {  
  let stack = [], maxScore = 0, score = 0;  
  for (let i = 0; i < str.length; i++) {    
    if (str[i] === '(') {
      stack.push(i);    
    } else if (str[i] === ')') {      
      let leftIndex = stack.pop();      
      if (leftIndex !== undefined) {        
        score = i - leftIndex - 1;      
      } else {        
        score = 0;      
      }      
      if (score > maxScore) {
        maxScore = score;        
      }    
    }  
  }  
  return maxScore;
}

2. 利用递归的思想

递归算法是将问题分解成子问题，然后逐步解决。

我们可以利用递归的思想分析字符串中的每个括号，找到其中的嵌套层数。

function findBracketScore(str) {  
  let maxScore = 0;  
  function findScore(subStr, score) {    
    if (subStr.indexOf('(') === -1) {      
      if (score > maxScore) {        
        maxScore = score;        
      }      
      return;    
    }    
    let leftIndex = subStr.lastIndexOf('(');    
    let rightIndex = subStr.indexOf(')', leftIndex);    
    let newSubStr = subStr.substring(leftIndex + 1, rightIndex);    
    findScore(newSubStr, score + 1);  
  }
  findScore(str, 0);  
  return maxScore;
}

三、对比两种方法的优缺点

对比两种方法，它们各有优缺点。

利用栈的方法，时间复杂度为O(n)，空间复杂度为O(n)，而递归的时间复杂度为O(n^2)，空间复杂度为O(n)。

使用栈的方法在代码实现上更为简单，能够快速定位到每个括号中的嵌套层数，但是需要额外的空间存储栈。

使用递归的方法不需要额外的空间，直接对字符串进行递归操作，但是由于每次递归都需要重新搜索左右括号的位置，时间复杂度比较高。

四、总结

括号分数是一个在程序开发中常用的概念，在JavaScript中查找括号分数可以利用栈的方法或递归的方法，两种方法各有优缺点，开发者需要根据实际情况选择。