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);
    } else if (closing.includes(char) && char !== map[stack.pop()]) {
      return false;
    }
  }
  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++;
    } 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;
};

Solution 3:

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

//stack
class STACK 
{
  //initialize
  constructor()
  {
    this.arr = [];
  }
  //add to stack
  add(data)
  {
    this.arr.push(data);
  }
  //remote from stack
  remove()
  {
    return this.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()
  {
    return this.arr[this.arr.length-1];
  }
  //check if empty
  empty()
  {
    if(this.arr.length===0)
      return true;
    else
      return false;
  }
}

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

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: ')'
  };

  function isBalanced(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) 
        return false;
    }

    return true;
  }
  
  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}';

function isBalanced(str) {
  let stack = [];
  let closeMap = new Map([
    [']', '['], 
    ['}', '{'], 
    [')', '(']
  ]);
  let openSet = new Set(closeMap.values());

  for (let ch of str) {
    if(closeMap.has(ch) && 
      (!stack.length || stack.pop() != closeMap.get(ch)))
        return false;            
    else if(openSet.has(ch)) 
      stack.push(ch);
    else continue;
  }

  return (!stack.length)
};

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