Find the corresponding closing parenthesis

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.

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

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

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