Algorithm: Optimizing 'balancing Brackets'

I have been posed the following question... Given a N different open and close braces in a string '( { [ } ] )', check whether the string has matching braces. Return true if the br

Solution 1:

Using Stack

The following solution has time complexity of O(n)

function isBalanced(str){
  const map = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const closing = Object.values(map);
  const stack = [];
        
  for (let char of str) {
    if (map[char]) {
      stack.push(char);
    } elseif (closing.includes(char) && char !== map[stack.pop()]) {
      returnfalse;
    }
  }
  return !stack.length;
}

Solution 2:

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)

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++;
    } elseif( enders.indexOf(braces[i]) !== -1 ){
      if(size === 0) { returnfalse; }
      var index = enders.indexOf(braces[i]);
      if(stack[size-1] === beginners[index] ){
        size --;
      } else {
        returnfalse;
      }
    }
  }

  return size === 0;
};

Solution 3:

This might be a stretch, but why not use a well defined stack. It's good practice.

//stackclassSTACK
{
  //initializeconstructor()
  {
    this.arr = [];
  }
  //add to stack
  add(data)
  {
    this.arr.push(data);
  }
  //remote from stack
  remove()
  {
    returnthis.arr.pop();
  }
  //print the stack
  print()
  {
    console.log('-----');
    for(let i = this.arr.length-1; i >=0; i--)
      console.log('|',this.arr[i],'|');
    console.log('-----');
  }
  //peek last element
  peek()
  {
    returnthis.arr[this.arr.length-1];
  }
  //check if empty
  empty()
  {
    if(this.arr.length===0)
      returntrue;
    elsereturnfalse;
  }
}

//Use stack to check for balanced paranthesisconst balanceParantheses = (str)=>{
  obj = new STACK();
  for(let char of str)
  {
    if(char==='[' || char==='{' || char ==='(')
      obj.add(char);
    else {
      switch(char)
      {
        case(']'):
          if(obj.empty())
            returnfalse;
          elseif(obj.peek()!=='[') {
            returnfalse
          } else obj.remove();
          break;
        case(')'):
          if(obj.empty())
            returnfalse;
          elseif(obj.peek()!=='(') {
            returnfalse
          } else obj.remove();
          break;
        case('}'):
          if(obj.empty())
            returnfalse;
          elseif(obj.peek()!=='{') {
            returnfalse
          } else obj.remove();
          break;
      }
    }
  }
  returntrue;
}

console.log(balanceParantheses("[()]{}{[()()]()}"));

Solution 4:

Use a counter variable (Source: Solution #3, Page 496, Fundamentals of Computer Programming with C#):

let openers = {
    curly: '{',
    square: '[',
    paren: '('
  };

  let closers = {
    curly: '}',
    square: ']',
    paren: ')'
  };

  functionisBalanced(str) {
    let counter = 0;

    for (let char of str) {
      if (char === openers.curly || char === openers.square || char === openers.paren)
        counter++;

      if (char === closers.curly || char === closers.square || char === closers.paren)
        counter--;

      if (counter < 0) 
        returnfalse;
    }

    returntrue;
  }
  
  console.log(isBalanced("[]"));
  console.log(isBalanced("]][[[][][][]]["));
  console.log(isBalanced("[][[[[][][[[]]]]]]"));
  console.log(isBalanced("]["));
  console.log(isBalanced("[[[]]]][[]"));
  console.log(isBalanced("[]][[]]][[[[][]]"));
  console.log(isBalanced("[[]][[][]]"));
  console.log(isBalanced("[[]]"));
  console.log(isBalanced("]][]][[]][[["));
  console.log(isBalanced("][]][][["));
  console.log(isBalanced("][]["));
  console.log(isBalanced("[[]]][][][[]]["));
  console.log(isBalanced(""));

Solution 5:

Here is my solution via Stack structure.

const input = '{a[b{c(d)e}f]g}';

functionisBalanced(str) {
  let stack = [];
  let closeMap = newMap([
    [']', '['], 
    ['}', '{'], 
    [')', '(']
  ]);
  let openSet = newSet(closeMap.values());

  for (let ch of str) {
    if(closeMap.has(ch) && 
      (!stack.length || stack.pop() != closeMap.get(ch)))
        returnfalse;            
    elseif(openSet.has(ch)) 
      stack.push(ch);
    elsecontinue;
  }

  return (!stack.length)
};

console.log('result is: ' + isBalanced(input));