Balanced Brackets

README.md

Balanced Brackets

Learning Objective

• Understand use cases for stacks

Interviewer Prompt

Write a function that determines whether an input string has balanced brackets.

You are given an input string consisting of brackets—square [ ], round ( ), and curly { }. The input string can include other text. Write a function that returns either true if the brackets in the input string are balanced or false if they are not. Balanced means that any opening bracket of a particular type must also have a closing bracket of the same type.

An empty input string or a string without brackets can also be considered "balanced".

Examples

hasBalancedBrackets('[][(){}'); // false
hasBalancedBrackets('({)}'); // false
hasBalancedBrackets('({[]})'); // true
hasBalancedBrackets('text ( is allowed ){rwwrwrrww [] ()}'); // true

Solutions

In general an optimal approach is to keep a stack of open brackets, pushing as we come across them. As we come across closing brackets, if they match the most-recently-opened bracket we can pop the most-recently-opened bracket. If our stack is empty once we reach the end of the string, then our brackets must have been balanced.

Here's a solid solution that runs iteratively for every bracket in our input:

const bracketPattern = /[[\](){}]/g;
// regex pattern to capture any of these symbols.
// "\" escapes the character after
const bracketPairs = {
// dictionary to keep track of the possible pairings
  '[' : ']',
  '(' : ')',
  '{' : '}'
};

const hasBalancedBrackets = (string) => {
  
  const matches = string.match(bracketPattern);
  // returns an array of all the brackets
  // in the input that match our regex pattern
  const bracketsStack = [];
  
  if (!string.length || !matches.length) return true;
  // empty input or no brackets i.e. 'balanced'
  // (throwing an error is fine also)
  
  matches.forEach((bracket) => {
    const lastBracket = bracketsStack[bracketsStack.length - 1];
    
    bracketPairs[lastBracket] === bracket ?
    // if the current bracket matches our dict with key of lastBracket
    
      bracketsStack.pop() :
      // pop from the current brackets stack
      
      bracketsStack.push(bracket);
      // else push it to the top of the stack
  });
  
  return bracketsStack.length === 0;
  // if the brackets were balanced then we should not have any brackets in the array
  
  // alternate:
  // return !bracketsStack.length
}

Without comments and condensed a little it would look like this:

const hasBalancedBrackets = (string) => (
  bracketPairs = { '[' : ']', '(' : ')', '{' : '}' },
  
  matches = string.match(/[[\](){}]/g),
  
  bracketsStack = [],
  
  !string.length || !matches.length ?
    true :
    (matches.forEach((bracket) => (
    lastBracket = bracketsStack[bracketsStack.length - 1],
    bracketPairs[lastBracket] === bracket ?
      bracketsStack.pop() :
      bracketsStack.push(bracket)
    )),
  
  !bracketsStack.length)
)

A more optimal solution would cut out early if it comes across a closing bracket that does not match the most recent open bracket. That could look something like:

const hasBalancedBrackets = str => {
  const bPairs = { '[' : ']', '(' : ')', '{' : '}' };
  const bStack = [];
  
  matches = str.match(/[[\](){}]/g);
  
  for (let el of matches) {
    if (el in bPairs) bStack.unshift(el);
    
    else if (bPairs[bStack[0]] === el) bStack.shift();
    
    else return false;
  }
  return !bStack.length;
};

Resources

• MDN docs on Regular Expressions (regex)
• AlgoExpert Link
• Structy has 3 similar variations

---