find the missing braces in a string javascript

Question

I have written the logic to check for parenthesis for "(" and ")" but there seems to an issue when parenthesis gets mixed. This is because I'm just comparing the total parenthesis count.

This is what i wrote

function checkParanthesis(str){
  var depth=0;
  for(var i in str){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[")
      depth++;
    else if(str[i] == ")" || str[i] == "}" || str[i] == "]")
      depth--;
  }
  
  if(depth !==0) return false;
  
  return true;
}

console.log(checkParanthesis("() test"));

Question:

But how can I check for multiple parenthesis elements? (){}[]

For example,

Input:

"[(]) abcd" // should return false
"[{()}] test" // should return true

Should return false (Not true)

Answer 1

Since I was working on leetCode and find your question, I found this article was written pretty clear about the problem and I tested it and I quoted here:

Click here! Parenthesis Matching Problem in JavaScript

let isMatchingBrackets = function (str) {
    let stack = [];
    let map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }

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

        // If character is an opening brace add it to a stack
        if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) {
            stack.push(str[i]);
        }
        //  If that character is a closing brace, pop from the stack, which will also reduce the length of the stack each time a closing bracket is encountered.
        else {
            let last = stack.pop();

            //If the popped element from the stack, which is the last opening brace doesn’t match the corresponding closing brace in the map, then return false
            if (str[i] !== map[last]) {return false};
        }
    }
    // By the completion of the for loop after checking all the brackets of the str, at the end, if the stack is not empty then fail
        if (stack.length !== 0) {return false};

    return true;
}

Answer 2

The array/stack/counter approach reads the string from left to right. Another approach is to work from the inside out.

function checkParanthesis(str){
  while ( str.indexOf('()')>=0 || str.indexOf('[]')>=0 || str.indexOf('{}')>=0 ) {
    str = str.replace('()','').replace('[]','').replace('{}','');
  }
  return str.length===0;
}

You could use regular expressions for the replace part to do a global replace and loop fewer times. The downside is that you'd need to escape everything in sight: str.replace(/\(\)/g,'') et.c.

Answer 3

Use a regex to get all the braces in a match() array...then remove each end of array testing each set

function checkParanthesis(str) {
  //hashmap to compare open/close braces
  var closers = {'[': ']','(': ')','{': '}'};
  // create braces array
  var parStack = str.match(/\(|\{|\[|\)|\}|\]/g) || [];

  if (parStack.length % 2 !== 0) {//must have even number
    return false;
  } else {
    while (parStack.length) {
      // check each end of array against each other.
      if (closers[parStack.shift()] !== parStack.pop()) {
        //mismatch , we're done
        return false;
      }
    }
    return true;
  }

}
console.log('no braces ', checkParanthesis("test"));
console.log('matched ', checkParanthesis("() test"));
console.log('mis matched ',checkParanthesis("[(]) abcd")); // should return false
console.log('matched ',checkParanthesis("[{()}] test"));

Answer 4

Use an array as a stack to keep track of unresolved opening braces:

function checkParanthesis(str){
  var stack=[];
  for(var i=0; i<str.length; i++){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[")
      stack.push(str[i]);
    else if(str[i] == ")") {
        if(stack.pop() != "(") { return false; }
    }
    else if(str[i] == "}") {
        if(stack.pop() != "{") { return false; }
    }
    else if(str[i] == "]") {
        if(stack.pop() != "[") { return false; }
    } 
  }

  return !stack.length;
}

You can probably clean this up to be more readable, but basically:

• Every time you find an opening brace, add it to the stack.
• Every time you see a closing brace, pop the stack and see if the stack's top is a matching opening brace.
  • If it's not, you have a mismatch, so you can immediately return false.
• If you make it to the end, you didn't spot any errors, return true if the stack is empty (i.e., stack.length is 0).

(Note I also changed your i in str loop since it will iterate over properties on String.prototype.)

One cleanup you could do (but I'm not sure if this makes the code more readable or not) would be to put the brace pairings in an object, with the closing character as the key and the corresponding opening character as the value. Then, see if the current character exists as a key in the object, and if so, pop the stack and see if the value for that key matches:

function checkParanthesis(str){
  var stack=[];
  var brace_pairings = { ")":"(", "}":"{", "]":"[" };
  for(var i=0; i<str.length; i++){
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") {
      stack.push(str[i]);
    } else if(str[i] in brace_pairings) {
        if(stack.pop() != brace_pairings[str[i]]) { return false; }
    }
  }

  return !stack.length;
}

Answer 5

Rather than a counter, you could use a stack, pushing a token onto the stack when an opening bracket is seen, and popping from the stack when the correct closing bracket is seen. If a closing bracket is encountered when a different type of bracket is at the top of the stack, or when the stack is empty, the string is unbalances.

Something like this (not polished and tested):

function checkParanthesis(str){
var stack = [];
var open;
for(var i in str){
  if(str[i] == "(" || str[i] == "{" || str[i] == "[") {
    stack.push(str[i]);
  }
  else if(str[i] == ")" || str[i] == "}" || str[i] == "]") {
    if ( stack.length == 0 ) {
       return false;
    }
    open = stack.pop();
    if (
       ( open == '(' && str[i] != ')' )
       || ( open == '[' && str[i] != ']' )
       || ( open == '{' && str[i] != '}' )
     ) {
       return false;
    }
  }
}

 if ( stack.length > 0 ) {
   return false;
 }

 return true;
}