给定表达式字符串exp，编写一个程序来检查exp中的
对和

"{","}","(",")","[","]"


的顺序是否正确。 />
例如，对于

exp = "[()]{}{[()()]()}"


该程序应打印true，对于

exp = "[(])"


该程序应打印false />
复杂度：


时间复杂度：\ $ O（n）\ $其中\ $ n \ $是字符串的长度
空间复杂度：\ $ O（\ frac {n} {2}）\ $其中\ $ n \ $是字符串的长度

我看到了Java版本，并以为“我想提交JavaScript版本。”寻找代码审查，优化和最佳实践。

在我的版本中，字符串可以包含除括号以外的其他字符，""被接受为输入，并且我并不关心短路奇数长度的字符串。 



function parenthesesAreBalanced(s)
{
  var parentheses = "[]{}()",
    stack = [], //Parentheses stack
    i, //Index in the string
    c; //Character in the string

  for (i = 0; c = s[i++];)
  {
    var bracePosition = parentheses.indexOf(c),
      braceType;
    //~ is truthy for any number but -1
    if (!~bracePosition)
      continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    if (braceType === 'closed')
    {
      //If there is no open parenthese at all, return false OR
      //if the opening parenthese does not match ( they should be neighbours )
      if (!stack.length || parentheses.indexOf(stack.pop()) != bracePosition - 1)
        return false;
    }
    else
    {
      stack.push(c);
    }
  }
  //If anything is left on the stack <- not balanced
  return !stack.length;
}

console.log('{}([]) true', parenthesesAreBalanced('{}([])'));
console.log('{{ false', parenthesesAreBalanced('{{'));
console.log('[(]) false', parenthesesAreBalanced('[(])'));
console.log("{}([]) true", parenthesesAreBalanced("{}([])"));
console.log("([}]) false", parenthesesAreBalanced("([}])"));
console.log("([]) true", parenthesesAreBalanced("([])"));
console.log("()[]{}[][]", parenthesesAreBalanced("()[]{}[][]"));


评论

添加此检查作为第一个验证，如果表达式的长度为奇数，我们可以立即返回false。
@Ananda支持非大括号，“ abc”和“ o []”平衡且长度奇数

#1 楼

这几乎是所有样式建议；代码本身看起来很棒。但是，这些只是偏好。我也跳过了按位操作，添加了一些严格的比较而不是!stack.length等，将i++移至其“常规”位置，并加长了一些变量名，以简化说明。

再次：基本上这都是毫无意义的，但是我只是喜欢把东西拼出来。

唯一真正的区别是，我将期望的闭合括号的位置推到了堆栈上，而不是将开始括号推到了堆栈上。 

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}




更新：实际上，您可以跳过内部条件中的一个stack.length检查；实际上，您可以跳过一个stack.pop()检查。如果堆栈为空，则undefined只会返回q4312079q，所以这就足够了：

if(stack.pop() !== bracePosition) {
  return false;
}


评论

\ $ \ begingroup \ $
我非常喜欢推动bracePosition + 1，+ 1的想法
\ $ \ endgroup \ $
– konijn
2014年4月2日在12:11


#2 楼

我编写了一个称为Balanced的Node / JavaScript库，它可以完成更多操作，但是我使用的主要概念是使用堆栈，编译open / close标签的正则表达式，然后进行1次传递。它似乎比indexOf的执行要好。

使用平衡的isBalanced方法编写方法的方式是
例外：JSFiddle和以下示例忽略注释块JSFiddle

对于您的示例，balanced将产生以下错误

function isBalanced(string) {
    return !!balanced.matches({source: string, open: ['{', '(', '['], close: ['}', ')', ']'], balance: true});
}


评论

\ $ \ begingroup \ $
我喜欢你的回答。但是，有一些故障。我认为您应该改进它，使其更好地解析整个JS函数或FILE。例如：在您的JS小提琴上，我粘贴了一条包含.replace（/ [{] / g，“”）.replace（/ [}] / g，“”）的JS行。它失败了。
\ $ \ endgroup \ $
– Manjeet
18-09-7在15:50