Balanced Characters Javascript

Question

I have this codewars exercise in which I have to write a piece of code to validate that a supplied string is balanced. For example, I need to make sure when I encounter an opening "(" then I'll have to make sure there's also closing ")" tag. However, in this code, a second string will contain the parentheses or characters for the first string to find and check.

Here is my code:

function isBalanced(s, caps) {
  let strArr = s.split("");
  let capsArr = caps.split("");

  let pairsCaps = caps.match(/.{1,2}/g);

  for(let i = 0; i < strArr.length; i++) {

    for (let m = 0; m < pairsCaps.length; m++){
    if(strArr[i] == pairsCaps[m][0] && strArr[strArr.length -1] == pairsCaps[m][1]) {
      return true;
    } else {
      return false;
    }
  }

  }
}
console.log(isBalanced("Sensei says -yes-!", "--"));

However, when I ran some sample tests, I found out that while it worked for isBalanced("(Sensei says yes!)", "()") and isBalanced("(Sensei [says] yes!)", "()[]"), the code wasn't working when there's -- in isBalanced("Sensei says -yes-!", "--") in which it returned false when it was supposed to return true.

I looked over my code but couldn't narrow down the problem. Please help...?

Can you provide the link to the CodeWars kata? – trincot Dec 01 '19 at 09:08 — trincot, Dec 01 '19 at 09:08

CertainPerformance · Answer 1 · 2019-12-01T08:53:05.003

Your code currently, when an opening tag is found, only checks to see if the final character in the string is the matching closing tag:

if(strArr[i] == pairsCaps[m][0] && strArr[strArr.length -1] == pairsCaps[m][1]) {

That's like saying "If the character being iterated over is (, check to see that the last character is )".

One option is to create a stack of currently open tags instead. When you find an opening tag, push it to the tag stack; when you find a closing tag, remove the top item from the tag stack if it matches. (If it doesn't match, the tags are unbalanced). If the stack has any elements in it at the end, the tags are unbalanced. Otherwise, it's balanced.

Another option is to construct a regular expression which matches an opening tag, followed by non-tag characters, followed by the closing tag. Repeatedly replace the match substring with nothing until the pattern doesn't match anymore, and check to see if the final result is the empty string:

// https://stackoverflow.com/questions/3561493/is-there-a-regexp-escape-function-in-javascript
const escape = s => s.replace(/[-\/\\^$*+?.()|[\]{}]/g, '\\$&');

function isBalanced(s, caps) {
  const openTags = [];
  const closeTags = [];
  for (const [index, char] of [...caps].entries()) {
    (index % 2 ? closeTags : openTags).push(char);
  }
  const pattern = new RegExp(
    openTags
      .map((openTag, i) => `${escape(openTag)}[^${escape(caps)}]*${escape(closeTags[i])}`)
      .join('|')
  );
  let str = s;
  let lastStr;
  while (lastStr !== str) {
    lastStr = str;
    str = str.replace(pattern, '');
  }
  return str.replace(new RegExp(`[^${caps}]*`), '') === '';
}
console.log(isBalanced("Sensei says -yes-!", "--"));
console.log(isBalanced("(Sensei says yes!)", "()"))
console.log(isBalanced("(Sensei [says] yes!)", "()[]"));
console.log(isBalanced("(Sensei [says] yes!", "()[]"));
console.log(isBalanced("Sensei [says] yes!)", "()[]"));

score 0 · Answer 2 · answered Dec 01 '19 at 08:54

It's an interesting problem because the opening and closing caps are the same in the second case. Try this on for size:

function isBalanced(s, caps){
    var unclosed = 0;
    for(var i = 0; i < s.length; i++){
        if(s.charAt(i) == caps.charAt(1) && unclosed > 0){
            unclosed--;
        }
        else if(s.charAt(i) == caps.charAt(0)){
            unclosed++;
        }
    }
    return unclosed == 0;
}
console.log(isBalanced("Sensei says -yes-!", "--"));

Note that this function checks for the opportunity to close a cap before it checks if it can open another one.

score 0 · Answer 3 · answered Dec 01 '19 at 09:42

The problem in your code is that you expect the closing bracket to always be in the final position, i.e. strArr[strArr.length -1].

Instead of looking forward, look backward to see if the previous encountered opening bracket matches the currently encountered closing bracket. And maintain a stack so you can manage nested brackets.

When pairs have the same opening and closing characters, assume that a second occurrence is always intended for closing. So make sure to first check whether the current character is closing a previously opened bracket, and only when that fails, check that the character is a closing character (at an odd position in caps):

function isBalanced(s, caps) {
    let closersStack = [];
    for (let ch of s) {
        let i = caps.indexOf(ch);
        if (i < 0) continue; // not an opener nor closer
        if (closersStack[closersStack.length-1] === ch) { // is closing
            closersStack.pop();
        } else if (i % 2 === 0) { // is opening
            closersStack.push(caps[i+1]); // push the expected closer
        } else return false; // mismatch: an unexpected closer
    }
    return !closersStack.length; // all openers should have been closed
}
// Some test cases
console.log(isBalanced("Sensei says -yes-!", "--"));
console.log(isBalanced("(Sensei says yes!)", "()"))
console.log(isBalanced("(Sensei [says] yes!)", "()[]"));
console.log(isBalanced("(Sensei [says] yes!", "()[]"));
console.log(isBalanced("Sensei [says] yes!)", "()[]"));

Note that this script relies on the fact that closersStack[-1] does not trigger an error, but gives undefined, which is always different from a single-character string.

Balanced Characters Javascript

3 Answers3