Reputation: 9782

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 braces match, false otherwise.

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

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.

Upvotes: 5

Answers (8)

Lior Elrom

Reputation: 20862

Using Stack

The following solution has a time complexity of O(n)

function isBalanced(str) {
  const stack = [];
  const map = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const closing = Object.values(map);

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

console.log(isBalanced('{[())}')); // false 
console.log(isBalanced('{[()]}')); // true

Upvotes: 11

ashish siddhu

Reputation: 219

The simple solution in JavaScript

Time complexity O(n)

/**
 * @param {string} s
 * @return {boolean}
 */
var checkParanthesis = function(s) {
    if(typeof s !== "string" || s.length % 2 !== 0) return false;
    let i = 0;
    let arr = [];
    while(i<s.length) {
        if(s[i]=== "{" || s[i]=== "(" || s[i]=== "[") {
           arr.push(s[i]);
        } else if(s[i] === "}" && arr[arr.length-1] === "{") {
            arr.pop()
        } else if(s[i] === ")" && arr[arr.length-1] === "(") {
            arr.pop()
        } else if(s[i] === "]" && arr[arr.length-1] === "[") {
            arr.pop()
        } else {
            return false;
        }
        i++
    }
    return arr.length === 0;
};
let str = "{([])}";
console.log(checkParanthesis(str))

Upvotes: 0

Shubham Vijay Vargiy

Reputation: 11

function isBalanced(str = "") {
    if (typeof str !== "string" || str.trim().length === 0) {
        return false;
    }
    str = str.replace(/[^{}()\[\]]/g, "");
    if (typeof str !== "string" || str.trim().length === 0) {
        return false;
    }
    while (str.length > 0) {
        let perviousLenght = str.length;
        str = str.replace(/\(\)/g, "");
        str = str.replace(/{}/g, "");
        str = str.replace(/["'\[]]/g, "");
        if (str.length === perviousLenght) {
            return false;
        }
    }
    return true;
}
console.log("Good Values ==>");
console.log(isBalanced("[()]"));
console.log(isBalanced("(function(){return [new Bears()]}());"));
console.log(isBalanced("var a = function(){return 'b';}"));
console.log(isBalanced("//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]}]"));
console.log("Bad Values ==>");
console.log(isBalanced("{"));
console.log(isBalanced("{]"));
console.log(isBalanced("{}("));
console.log(isBalanced("({)()()[][][}]"));
console.log(isBalanced("(function(){return [new Bears()}())];"));
console.log(isBalanced("var a = [function(){return 'b';]}"));
console.log(isBalanced("/*Comment: a = [} is bad */var a = function({)return 'b';}"));
console.log(isBalanced("/*[[[ */ function(){return {b:(function(x){ return x+1; })'c')}} /*_)(([}*/"));
console.log(isBalanced("//Complex object;\n a = [{a:1,b:2,c:[ new Car( 1, 'black' ) ]]"));

Upvotes: 0

Buzzy

Reputation: 1924

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

Upvotes: 0

Benjamin Livinus

Reputation: 39

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(""));

Upvotes: 0

Kunle Babatunde

Reputation: 19

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("[()]{}{[()()]()}"));

Upvotes: 0

Alejandro

Reputation: 2326

This was my take on the problem:

const isBalance = str => {
  const result = !str.split('').reduce((accum, current) => {
    if (accum < 0) return accum
    else {
      if (current === '(') return accum+= 1
      if (current === ')') return accum-= 1
      if (current === '[') return accum+= 2
      if (current === ']') return accum-= 2
      if (current === '{') return accum+= 3
      if (current === '}') return accum-= 3    
    }

  }, 0)

  return result
}

This solution will give you O(n). One thing that could improve this solution is if we reach accum < 0 (meaning that there is a closed brace that doesn't match anywhere), immediately you can stop iterating.

Plus it's much easier to read the code

Upvotes: -1

iagowp

Reputation: 2494

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

Upvotes: 3

Algorithm: optimizing &#39;balancing brackets&#39;

Answers (8)

Using Stack

Time complexity O(n)

Related Questions

Algorithm: optimizing 'balancing brackets'