3
\$\begingroup\$

Problem:

"Sometimes (when I nest them (my parentheticals) too much (like this (and this))) they get confusing."

Write a function that, given a sentence like the one above, along with the position of an opening parenthesis, finds the corresponding closing parenthesis. For the above input string and position 10 the algorithm should output 76.

After some trial and error I am able to come up with an algorithm.

function findClosingBracketMatchIndex(str, pos) {
  let openBracketCount = 0;
  let givenBracketPosition = -1;
  let index = -1;
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (char === '(') {
      openBracketCount++;
      if (i === pos) {
        givenBracketPosition = openBracketCount;
      }
    } else if (char === ')') {
      if (openBracketCount === givenBracketPosition) {
        index = i;
        break;
      }
      openBracketCount--;
    }
  }
  return index;
}

console.log(findClosingBracketMatchIndex('a (bc)', 2)); // 5
console.log(findClosingBracketMatchIndex('a (b ())', 2)); // 7
console.log(findClosingBracketMatchIndex('a (b ())', 5)); // 6
console.log(findClosingBracketMatchIndex('(a (b ()))', 0)); //9

Expert advice:

Apart from code review I would like to know if there are some tips to check the correctness of such algorithms, including off-by one error and conditions.

\$\endgroup\$
3
\$\begingroup\$

You might want to confirm that the character at the given position is indeed a (.

There is no reason to care about what appears before the given position. You can start examining the string starting at pos + 1. Once you have found the the position of the matching closing parenthesis, you can just return it right away; there is no need to ever set index.

function findClosingBracketMatchIndex(str, pos) {
  if (str[pos] != '(') {
    throw new Error("No '(' at index " + pos);
  }
  let depth = 1;
  for (let i = pos + 1; i < str.length; i++) {
    switch (str[i]) {
    case '(':
      depth++;
      break;
    case ')':
      if (--depth == 0) {
        return i;
      }
      break;
    }
  }
  return -1;    // No matching closing parenthesis
}

console.log(findClosingBracketMatchIndex('a (bc)', 2)); // 5
console.log(findClosingBracketMatchIndex('a (b ())', 2)); // 7
console.log(findClosingBracketMatchIndex('a (b ())', 5)); // 6
console.log(findClosingBracketMatchIndex('(a (b ()))', 0)); //9

\$\endgroup\$
  • \$\begingroup\$ I forgot but it was mentioned that the input contains correct number of parenthesis. I think I must update the question. \$\endgroup\$ – CodeYogi Nov 2 '17 at 22:22
  • \$\begingroup\$ Any personal preference/suggestion using switch over if? \$\endgroup\$ – CodeYogi Nov 2 '17 at 22:25
  • \$\begingroup\$ switch makes it immediately obvious that the decision of which branch to take depends solely on str[i], whereas multiple if statements could each contain arbitrary conditions. On some languages / interpreters, switch might lead to optimizations being applied. \$\endgroup\$ – 200_success Nov 2 '17 at 22:31
  • \$\begingroup\$ I am still in learning phase so, what was your thought process? any structured way or just intuition? I followed intuition. \$\endgroup\$ – CodeYogi Nov 3 '17 at 6:01
  • \$\begingroup\$ suppose if there is array of string then what should be done for example if we have array like ['a','(','b',')']? \$\endgroup\$ – Shyam Jun 6 at 11:10
1
\$\begingroup\$

Not a bad start, however there are a few things that I would recommend changing.

  1. Don't scan from the start of the string. You don't care about what happens before the bracket you start at and starting at the beginning of the string will slow down the function.

  2. Currently the function will return -1 if the caller specifies the position of a character which is not a bracket. I would argue that an exception should be thrown instead as this is clearly not desired behavior.

  3. It might be worth accepting an optional third parameter, the bracket type to match in the form of a tuple [opening, closing].

  4. Personal preference: Instead of storing index outside of the loop and breaking when a matching bracket is found, return immediately upon finding the matching bracket and add an additional return -1 outside the loop, this makes it easier for someone looking at the code to tell what happens if a matching bracket is not found.

With this in mind, here's the implementation I would use for the (, ) case.

function findClosingBracketIndex(str, pos) {
  if (str[pos] !== '(') {
    throw new Error('The position must contain an opening bracket');
  }
  let level = 1;
  for (let index = pos + 1; index < str.length; index++) {
    if (str[index] === '(') {
      level++;
    } else if (str[index] === ')') {
      level--;
    }
    
    if (level === 0) {
      return index;
    }
  }
  return -1;
}

console.log(findClosingBracketIndex('a (bc)', 2)); // 5
console.log(findClosingBracketIndex('a (b ())', 2)); // 7
console.log(findClosingBracketIndex('a (b ())', 5)); // 6
console.log(findClosingBracketIndex('(a (b ()))', 0)); // 9
console.log(findClosingBracketIndex('(a (b ())', 0)); // -1

Or an implementation accepting the brackets array:

function findClosingBracketIndex(str, pos, brackets = ['(', ')']) {
  if (str[pos] !== brackets[0]) {
    throw new Error('The position must contain an opening bracket');
  }
  let level = 1;
  for (let index = pos + 1; index < str.length; index++) {
    if (str[index] === brackets[0]) {
      level++;
    } else if (str[index] === brackets[1]) {
      level--;
    }
    
    if (level === 0) {
      return index;
    }
  }
  return -1;
}

console.log(findClosingBracketIndex('a (bc)', 2)); // 5
console.log(findClosingBracketIndex('a (b ())', 2)); // 7
console.log(findClosingBracketIndex('a (b ())', 5)); // 6
console.log(findClosingBracketIndex('(a (b ()))', 0)); // 9
console.log(findClosingBracketIndex('(a (b ())', 0)); // -1

\$\endgroup\$
  • \$\begingroup\$ Regarding the second point, I am still not clear on throwing exception, please explain. \$\endgroup\$ – CodeYogi Nov 2 '17 at 22:24
  • 1
    \$\begingroup\$ @CodeYogi essentially, findClosingBracketIndex('asdf', 0) will return -1 with your current implementation, I would expect it to throw as a is not a valid bracket. \$\endgroup\$ – Gerrit0 Nov 2 '17 at 22:53
0
\$\begingroup\$

Follow instructions.

Both answers (in my opinion) are wrong, as they have not followed the instructions and added additional behaviours not specified in the instructions.

The question is very clear as to what the function should do

"...given a sentence like the one above, along with the position of an opening parenthesis, finds the corresponding closing parenthesis."

Don't test if not specified.

The instructions indicate that the position of an opening parenthesis is given, not that you should test for an opening parenthesis, nor does it indicate that a parenthesis should be there.

If the return is not defined then it is undefined

There is also no indication of the return if their is no closing parenthesis. To return a number is not correct as that is a position (negatives sometimes indicate a search from the end of a string) and you do not know what is to be done with the return value.

The only valid return is undefined if there is no closing parenthesis

Never throw unless instructed to.

Not in the OP's code but as the given answers show it I must say something.

You should never take it upon yourself to throw if the instructions do not explicitly indicate that you should. Let javascript take care of any errors.

The expected results.

The behaviour expected is subtle but important, that the returned position is the closing parenthesis in the current nest at pos. This is explicit in the instructions.

eg

var s = "test (this ( is ) a ) test"
//            ^<-5  ^<-11    ^<-20
// For vals 5 to 10 and 17 to 19 the return should be 20
// For vals 11 to 15 the return should be 16
// For all other positions the return is  undefined

An example

There are many ways to write this function. I have opted for speed.

In javascript string searches are slow when you use character by character searches. You can speed up the search by using regular expressions. (Though it does not reduce complexity it does give significant performance increase)

function findClosingBracket(str, pos) {
  const rExp = /\(|\)/g;
  rExp.lastIndex = pos + 1;
  var deep = 1;
  while ((pos = rExp.exec(str))) {
    if (!(deep += str[pos.index] === "(" ? 1 : -1 )) { return pos.index }
  }
}


log("---");log("test 1");
const s = "test (this ( is ) a ) test";
log(findClosingBracket(s,-1)); // undefined
log(findClosingBracket(s,50)); // undefined
log(findClosingBracket(s,4));  // undefined
log(findClosingBracket(s,21)); // undefined
log(findClosingBracket(s,5));  // 20
log(findClosingBracket(s,18));  // 20
log(findClosingBracket(s,11));  // 16
log(findClosingBracket(s,"11")); // undefined
log(findClosingBracket(s,"not a number"));  // undefined
log(findClosingBracket({},10));  // undefined
log(findClosingBracket(s));  // undefined
log(findClosingBracket());  // undefined


log("---");log("test 2");
const s1 = " test this ( is ) a ) test";
log(findClosingBracket(s1,-1)); // 20
log(findClosingBracket(s1,50)); // undefined
log(findClosingBracket(s1,4));  // 20
log(findClosingBracket(s1,21)); // undefined
log(findClosingBracket(s1,5));  // 20
log(findClosingBracket(s1,18));  // 20
log(findClosingBracket(s1,11));  // 16


function log(data) { console.log(data) }

\$\endgroup\$
  • \$\begingroup\$ I would say that -1 seems fine because the caller must be expecting the number in between the range [0...length-1] although you made a correct point in saying -1 could be a valid index but I am not sure in javascript. \$\endgroup\$ – CodeYogi Nov 3 '17 at 16:06
  • \$\begingroup\$ @CodeYogi substr takes negative values. Many functions now assign default parameters eg function doSomething(a = foo){ that require an undefined for the default to be assigned. But the point is that the instructions did not specify the return, it is undefined and thus you default to undefined. \$\endgroup\$ – Blindman67 Nov 3 '17 at 17:12
  • 1
    \$\begingroup\$ Returning -1 to indicate "not found" follows the convention established by String.indexOf(). Returning undefined risks confusion with 0; this is a common gotcha with PHP's strpos() (see the Warning in the docs). This question did not quote exactly what the requirements of the challenge were. If it returns -1 to indicate "not found", I wouldn't challenge it. \$\endgroup\$ – 200_success Nov 3 '17 at 17:48
  • \$\begingroup\$ @200_success undefined allows for default parameters const [foo = log("Error")] = [fooSomething()]; Undefined is the convention for an unknown. String.indexOf is a pain, it should return undefined so that we can simplify its use. \$\endgroup\$ – Blindman67 Nov 3 '17 at 18:00
  • \$\begingroup\$ @200_success well the question is a programming challenge from some source and I could constraints of my own but then that would not be fair. The requirement are all given in the question and rest I think is left for discussion. \$\endgroup\$ – CodeYogi Nov 3 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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