在字符串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"));

题:

但是,如何检查多个括号元素？(){} []

例如,

输入:

"[(]) 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.)

你可以做的一次清理(但我不确定这是否会使代码更具可读性)是将大括号配对放在一个对象中,关闭字符作为键,相应的开头字符作为值.然后,查看当前字符是否作为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;
}

Answer 2

您可以使用堆栈,在看到开口支架时将令牌推入堆栈,而在看到正确的关闭括号时从堆栈弹出,而不是计数器.如果在堆栈顶部有不同类型的支架时遇到关闭括号,或者当堆栈为空时,则该字符串是不平衡的.

像这样的东西(没有抛光和测试):

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

 if ( stack.length > 0 ) {
   return false;
 }

 return true;
}