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

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 2

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

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"));