39
\$\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\$
  • \$\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 '18 at 9:37
  • 1
    \$\begingroup\$ @Ananda this supports non braces, "abc" and "o[]" are balanced and odd length \$\endgroup\$ – konijn Oct 29 '18 at 12:48
32
\$\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\$
  • 3
    \$\begingroup\$ I very much like the idea of pushing the bracePosition+1, +1 \$\endgroup\$ – konijn Apr 2 '14 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\$
  • \$\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\$ – Alex Sep 7 '18 at 15:50

protected by 200_success Mar 24 '16 at 17:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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