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.

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.

• javascript
• algorithm

• use only a single variable brace, curl and par and increment decrement it. In the end just check if all are == to 0. – Haris Commented Jan 19, 2016 at 4:57
• 4 What is the definition for "matching braces"? To me, [()] is okay, [(]) is not. Your code checks for the latter; for the former, you would need a stack. – Amadan Commented Jan 19, 2016 at 5:03
• 1 Perhaps you want codereview.stackexchange.com if you're just looking for ways to improve your working code. – jfriend00 Commented Jan 19, 2016 at 5:09
• @jfriend00: You're missing an x in eXchange. However, the current code isn't correct (if [(]) is invalid), and therefore might be off-topic on CR. – Zeta Commented Jan 19, 2016 at 5:11
• @Zeta - The OP says the code works, so that's what I was going by. – jfriend00 Commented Jan 19, 2016 at 5:13

8 Answers 8

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

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

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

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

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

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' ) ]]"));

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

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