算法：优化“平衡括号”

小编典典

算法：优化“平衡括号”

algorithm

我被提出以下问题…

给定字符串“（{{[}]）中N个不同的打开和关闭大括号，请检查字符串是否具有匹配的大括号。如果大括号匹配，则返回true，否则返回false。

这是我想出的答案…

function braceeql(braces){
  var leftpar = 0; 
  var rightpar = 0; 
  var leftbrace = 0;
  var rightbrace = 0;
  var leftcurl = 0;
  var rightcurl = 0;

  for(var index = 0; index < braces.length; index++){
    if(braces[index] == ')'){
      leftpar += 1;
    }else if(braces[index] == '('){
      rightpar += 1;
    }else if(braces[index] == '['){
      leftbrace += 1;
    }else if(braces[index] == ']'){
      rightbrace += 1;
    }else if(braces[index] == '{'){
      leftcurl += 1;
    }else if(braces[index] == '}'){
      rightcurl += 1;
    }
  }
  if(leftcurl == rightcurl && leftbrace == rightbrace && leftpar == rightpar){
    console.log(true)
  }else{
    console.log(false)
  }
}

这确实是一段繁琐的代码，但是可以肯定地工作。我对其他人如何解决此问题的看法不尽相同，但我想知道
是否存在一种更好/更干净的方法来解决此算法而不损害大O？

我非常乐于接受建议和其他解决此问题的方法。

阅读 286

2020-07-28

共1个答案

小编典典

好吧，首先，您的解决方案似乎并未涵盖）（] [或（{）}之类的问题（我不确定您是否被要求这样做，但是据我所知，这是玩具问题）

这是我一年多以前解决的这个玩具问题的解决方案，但是它看起来更快（如果不匹配，它将更早停止，如果ifs和else更少，并且重复的代码更少），但是我不确定更干净，因为从新手的角度来看，ifs和else更容易理解

var braceeql = function(braces){
  var stack = {};
  var size = 0;
  var beginners = ['(', '[', '{'];
  var enders = [')', ']', '}'];
  for(var i = 0; i < braces.length; i++){
    if( beginners.indexOf(braces[i]) !== -1 ){
      stack[size] = braces[i];
      size++;
    } else if( enders.indexOf(braces[i]) !== -1 ){
      if(size === 0) { return false; }
      var index = enders.indexOf(braces[i]);
      if(stack[size-1] === beginners[index] ){
        size --;
      } else {
        return false;
      }
    }
  }

  return size === 0;
};

2020-07-28