Balanced parentheses

Question

Given an expression string exp, write a program to examine whether the pairs and the orders of

"{","}","(",")","[","]"

are correct in exp.

For example, the program should print true for

exp = "[()]{}{[()()]()}"

and false for

exp = "[(])"

Complexity:

• Time complexity: \$O(n)\$ where \$n\$ is length of string
• Space complexity: \$O(\frac{n}{2})\$ where \$n\$ is length of string

I saw the Java version and thought "I want to submit a JavaScript version." Looking for code review, optimizations, and best practices.

In my version, the string can contain other characters than parentheses, "" is accepted as input, and I did not care about short circuiting odd length strings.

function parenthesesAreBalanced(s)
{
  var parentheses = "[]{}()",
    stack = [], //Parentheses stack
    i, //Index in the string
    c; //Character in the string

  for (i = 0; c = s[i++];)
  {
    var bracePosition = parentheses.indexOf(c),
      braceType;
    //~ is truthy for any number but -1
    if (!~bracePosition)
      continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    if (braceType === 'closed')
    {
      //If there is no open parenthese at all, return false OR
      //if the opening parenthese does not match ( they should be neighbours )
      if (!stack.length || parentheses.indexOf(stack.pop()) != bracePosition - 1)
        return false;
    }
    else
    {
      stack.push(c);
    }
  }
  //If anything is left on the stack <- not balanced
  return !stack.length;
}

console.log('{}([]) true', parenthesesAreBalanced('{}([])'));
console.log('{{ false', parenthesesAreBalanced('{{'));
console.log('[(]) false', parenthesesAreBalanced('[(])'));
console.log("{}([]) true", parenthesesAreBalanced("{}([])"));
console.log("([}]) false", parenthesesAreBalanced("([}])"));
console.log("([]) true", parenthesesAreBalanced("([])"));
console.log("()[]{}[][]", parenthesesAreBalanced("()[]{}[][]"));

Answer 1

This is almost all style suggestions; the code itself looks great.

Personally, I prefer the brace-on-same-line style for everything in JS, and I prefer proper blocks instead of inlining expressions. But those are just preferences. I've also skipped the bitwise trick, added some strict comparisons instead of !stack.length etc., moved the i++ over to its "usual" place, and lengthened a few variable names, just for clarity.

Again: This is all basically pointless, but I just like spelling things out.

The only real difference is that rather than push the opening brace onto the stack, I push the position of the expected closing brace. It just makes the conditional a bit cleaner later on.

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

---

Update: Actually, you can skip one stack.length check in the inner conditional; stack.pop() will just return undefined if the stack's empty, so this is enough:

if(stack.pop() !== bracePosition) {
  return false;
}

Answer 2

I wrote a Node/JavaScript library called balanced that can do this and much more, but the main concept I used was using a stack, compiling a regexp of the open/close tags, and then doing 1 pass. It seemed to perform better than indexOf implementations.

The way you would write your isBalanced method using balanced is

function isBalanced(string) {
    return !!balanced.matches({source: string, open: ['{', '(', '['], close: ['}', ')', ']'], balance: true});
}

Here's a live example with exceptions: JSFiddle and heres an example ignoring comment blocks JSFiddle

For your example balanced will produce the following error

Balanced: mismatching close bracket, expected ")" but found "]" at 1:3

1: [(])
-----^