javascript - 在字符串javascript中找到缺少的大括号

Question

我已经编写了检查“(”和“)”括号的逻辑，但是当括号混合时似乎出现了问题。这是因为我只是在比较括号总数。

这是我写的

function checkParanthesis(str){
  var depth=0;
  for(var i in str){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[")
      depth++;
    else if(str[i] == ")" || str[i] == "}" || str[i] == "]")
      depth--;
  }
  
  if(depth !==0) return false;
  
  return true;
}

console.log(checkParanthesis("() test"));

问题:

But how can I check for multiple parenthesis elements? (){}[]

例如，

输入:

"[(]) abcd" // should return false
"[{()}] test" // should return true

应该返回 false(不正确)

Answer 1

使用数组作为堆栈来跟踪未解析的左大括号:

function checkParanthesis(str){
  var stack=[];
  for(var i=0; i<str.length; i++){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[")
      stack.push(str[i]);
    else if(str[i] == ")") {
        if(stack.pop() != "(") { return false; }
    }
    else if(str[i] == "}") {
        if(stack.pop() != "{") { return false; }
    }
    else if(str[i] == "]") {
        if(stack.pop() != "[") { return false; }
    } 
  }

  return !stack.length;
}

您可能可以清理它以提高可读性，但基本上:

• 每次找到左大括号时，将其添加到堆栈中。
• 每次看到右大括号时，弹出堆栈并查看堆栈的顶部是否是匹配的左大括号。
  • 如果不是，则说明不匹配，因此可以立即返回 false。
• 如果你走到最后，你没有发现任何错误，返回 true 如果堆栈为空(即 stack.length 是 0).

(请注意，我还更改了 i in str 循环，因为它将遍历 String.prototype 上的属性。)

您可以做的一个清理工作(但我不确定这是否会使代码更具可读性)是将大括号对放在一个对象中，以结束字符作为键，相应的开始字符作为键值(value)。然后，查看当前字符是否作为键 in 对象存在，如果存在，弹出堆栈并查看该键的值是否匹配:

function checkParanthesis(str){
  var stack=[];
  var brace_pairings = { ")":"(", "}":"{", "]":"[" };
  for(var i=0; i<str.length; i++){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") {
      stack.push(str[i]);
    } else if(str[i] in brace_pairings) {
        if(stack.pop() != brace_pairings[str[i]]) { return false; }
    }
  }

  return !stack.length;
}