javascript - 如何计算没有匹配的嵌套括号？

Question

我正在计算不匹配的括号总数。

input:  text = “(()”
output: 1

input:  text = “(())”
output: 0

input:  text = “())(”
output: 2

我已经尝试了以下方法，但它不起作用:

let isMatchingBrackets = function(str) {
  let stack = [];
  let count = 0;

  for (let i in str.length) {
    if (str[i] === "(") {
      stack.push(str[i])
    } else if (str[i] === ")") {
      let tem = map.stack(x => x)
      if (tem !== ")") {
        count += 1;
      } else {
        stack.pop();
      }
    }
  }

  return stack.length + count
}

console.log(isMatchingBrackets("(()"))
console.log(isMatchingBrackets("(())"))
console.log(isMatchingBrackets("())("))

Answer 1

首先，你的迭代是错误的。您需要使用 for (let i = 0; i < str.length; i++)迭代一系列索引。

接下来，if (tem !=== ")")没有意义，因为数组永远不会等于字符串。您要检查的是堆栈是否为空。如果你有 )如果堆栈为空，则表示它不匹配。

不需要 tem变量。

let isMatchingBrackets = function(str) {
  let stack = [];
  let count = 0;

  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      stack.push(str[i])
    } else if (str[i] === ")") {
      if (stack.length === 0) {
        count += 1;
      } else {
        stack.pop();
      }
    }
  }

  return stack.length + count
}

console.log(isMatchingBrackets("(()"))
console.log(isMatchingBrackets("(())"))
console.log(isMatchingBrackets("())("))

但您实际上根本不需要堆栈。您只需计算左括号的数量，并在获得匹配的右括号时递减该计数器。

let isMatchingBrackets = function(str) {
  let open_count = 0;
  let close_count = 0;

  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      open_count++;
    } else if (str[i] === ")") {
      if (open_count === 0) {
        close_count ++;
      } else {
        open_count--;
      }
    }
  }

  return open_count + close_count;
}

console.log(isMatchingBrackets("(()"))
console.log(isMatchingBrackets("(())"))
console.log(isMatchingBrackets("())("))