balanced-brackets.md

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

When we iterate through a string of brackets, we want each left/open bracket to be paired with its corresponding closing bracket, with either balanced brackets or nothing in between.

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:

const bracketPattern = /[[\](){}]/g; // regular expression that matches with any of our required brackets
const bracketPairs = { //keeps track of the possible bracket pairings
  '[' : ']',
  '(' : ')',
  '{' : '}'
};
function hasBalancedBrackets (inputString) {
  const inputBrackets = inputString.match(bracketPattern); // returns an array of all the brackets in the input
  const brackets = []; // our stack of brackets! Will only keep open (left) brackets
  if (!inputString.length || !inputBrackets.length ) {
    return true; // empty input or no brackets i.e. 'balanced' (throwing an error is fine also)
  }
  if (inputBrackets.length % 2 !== 0) return false; // an odd number of brackets can't be balanced!
  
  for (let i = 0; i < inputBrackets.length; i++) {
    if (bracketPairs[inputBrackets[i]]) { // the current bracket is open
      brackets.push(inputBrackets[i])
    } else { // closed bracket
      if (bracketPairs[brackets[brackets.length -1]] === inputBrackets[i]) {
        // if most recent bracket matches with topmost bracket in our stack, we can remove the top bracket from our staff and move on.
        brackets.pop();
      } else {
        // if they're not a match, game over! Unbalanced brackets.
        return false;
      }
    }
  }
  return brackets.length === 0; // if the brackets were balanced then we should not have any brackets in the array
}

Another approach, slightly different:

const opens = {};
const closes = {};
([
  ['{', '}'],
  ['[', ']'],
  ['(', ')'],
]).forEach(([open, close]) => {
  opens[open] = close;
  closes[close] = open;
});

function hasBalancedBrackets (str) {
  const opensStack = [];
  for (const ch of str) {
    if (opens.hasOwnProperty(ch)) {
      opensStack.push(ch);
    } else if (closes.hasOwnProperty(ch)) {
      const mostRecentOpen = opensStack.pop();
      const correspondingClose = opens[mostRecentOpen];
      if (ch !== correspondingClose) return false;
    }
  }
  return opensStack.length === 0;
}

Here is another similar solution:

  const bracketPattern = /[[\](){}]/g;
  const bracketPairs = {
    '[' : ']',
    '{' : '}',
    '(' : ')'
  };
  
  const hasBalancedBrackets = str => {
  const bracketStack = [];
  strArr = str.match(bracketPattern);
  for(let i = 0; i < strArr.length; i++){
    if(strArr[i] in bracketPairs) bracketStack.unshift(strArr[i]);
    else if (bracketPairs[bracketStack[0]] === strArr[i]) bracketStack.shift();
    else return false;
  }
  return !bracketStack.length;
};