JS - 如何找到最深的一对括号的索引？

Question

我有一个字符串： "5 * ((6 + 2) - 1)" 我需要找到最深的一对括号及其内容。

我在谷歌上搜索了很多，但找不到任何特定于查找索引的信息。很多解决方案发现有多少级别，诸如此类，但没有什么真正有用的。本来想数层数，然后循环求解，反复求解直到完成，但是好像这样真的很慢

我不知道从哪里开始，所以我还没有写任何代码。

我要一个函数return 5、最深括号集合的字符串索引。我还需要为最深的“）”做同样的事情，因为我需要这对。示例：

const deepestPair = (str) => {
    // Find deepest pair of parentheses
}
deepestPair("(2(5)4)(3)") // Returns [2, 4], the indexes of the deepest open/close parentheses

Answer 1

您可以检查左括号和右括号并使用计数器来获取嵌套次数最多的索引。

const deepestPair = str => {
    var indices,
        max = 0,
        count = 0,
        last;
    
    [...str].forEach((c, i) => {
        if (c === '(') {
            last = i;
            count++;
            return;
        }
        if (c === ')') {
            if (count > max) {
                indices = [last, i];
                max = count;
            }
            count--;
        }
    });    
    return indices;
}

console.log(deepestPair("(2(5)4)(3)")); // [2, 4]

Answer 2

您可以使用 RegExp ([(])[^()]+[)] 来匹配 ( 后跟一个或多个非 ( 或 ) 的字符并结束 ), /[)]/ 匹配右括号, return 匹配索引

const deepestPair = (str, index = null) => 
  [index = str.match(/([(])[^()]+[)]/).index
  , str.slice(index).match(/[)]/).index + index]

console.log(deepestPair("(2(5)4)(3)"));

Answer 3

这是使用两个堆栈获得 最深对的简单方法。它还 returns 结构中对的深度，具有 open 和 close 索引。

它使用 singles 堆栈来保存到目前为止找到的左括号，并使用另一个堆栈 (pairs) 来保存匹配的括号。

每次找到一个右括号，最后一个左括号从 singles 堆栈中弹出并放入 pairs.

然后您只需要使用 depth 属性对这个 pairs 堆栈进行排序并获得第一项。

const deepestPair = str => { const singles = []; const pairs = []; [...str].forEach((c, i) => { if (c === '(') { singles.push({ depth: singles.length + 1, open: i }); } else if (c === ')' && singles.length) { pairs.push({ ...singles.pop(), close: i }); } }) pairs.sort((a, b) => b.depth - a.depth); return pairs.length ? pairs[0] : {}; }; console.log(deepestPair('(2(5)4)(3)')); console.log(deepestPair('(2(5)(1)(11(14))4)(3)'));

如果你想得到一个数组作为结果，你可以用这个替换最后一行：

return pairs.length ? [pairs[0].open, pairs[0].close] : [];

JS - 如何找到最深的一对括号的索引？

JS - How to find the index of deepest pair of parentheses?

javascript

nested

parentheses