算法:优化“平衡括号" [英] Algorithm: optimizing 'balancing brackets'

问题描述

我已经提出了以下问题...

I have been posed the following question...

给字符串({{}])中的N个不同的大括号，检查字符串是否具有匹配的大括号.如果大括号匹配，则返回true，否则返回false.

这是我想出的答案...

Here is the answer I came up with...

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?

This is really meaty piece of code, but it sure as heck works. I am seeing differing opinions about how others attacked this problem, but am left wondering is there a better/cleaner way of solving this algorithm without compromising the big O?

我非常乐意提出解决此问题的建议和其他方式.

I am very open to suggestions and other ways of looking at this problem.

推荐答案

首先，您的解决方案似乎没有涵盖)(] [或({)}之类的情况(我不确定您是否要求这样做，但据我所知，这是玩具问题，要求这样做)

Well, first of all, your solution doesn't seem to cover cases like )(][ or ({)} (I'm not sure you were asked to do it, but this toy problem as I know it requests it)

这是我一年多以前解决的玩具问题的一种解决方案，但是它看起来更快(如果不匹配，它会更早停止，if和else更少)并且重复的代码更少，但是我不确定更清洁，仿佛从新手的角度来看更容易理解

This is a solution for this toy problem I made over a year ago, but it seems faster(it will stop earlier if it doesnt match, has less ifs and elses) and repeats less code, but I'm not sure about cleaner, as ifs and elses are easier to understand from a novice point of view

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;
};

这篇关于算法:优化“平衡括号"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！