43
\$\begingroup\$

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("()[]{}[][]"));
\$\endgroup\$
2
  • \$\begingroup\$ add this check as the first validation, If the length of the expression is an odd number we can return false right away. \$\endgroup\$
    – Ananda
    Oct 29, 2018 at 9:37
  • 1
    \$\begingroup\$ @Ananda this supports non braces, "abc" and "o[]" are balanced and odd length \$\endgroup\$
    – konijn
    Oct 29, 2018 at 12:48

2 Answers 2

34
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ I very much like the idea of pushing the bracePosition+1, +1 \$\endgroup\$
    – konijn
    Apr 2, 2014 at 12:11
4
\$\begingroup\$

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: [(])
-----^
\$\endgroup\$
1
  • \$\begingroup\$ I like your answer. But, there are some glitches. I think you should improve it and make it better to parse whole JS function or FILE. For example: On your JS fiddle i pasted a JS line containing .replace(/[{]/g, "").replace(/[}]/g, "") . And it failed. \$\endgroup\$
    – Manjeet
    Sep 7, 2018 at 15:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.