How do you check if a string of brackets is valid (balanced parentheses)?

Think of a stack of plates in a hostel mess. You can only take the plate from the top, the one put down last. Brackets work the same way: the bracket opened most recently must be the first one closed.

In ( [ ] ), the [ opened last, so ] must close it before ) can close (. In ( [ ) ], the ) arrives while [ is still open, so the string is invalid. A stack remembers the order of open brackets for us.

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" }; // closing -> opening
  const stack = [];

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch); // remember the open bracket
    } else {
      // ch is a closing bracket: the latest open one must match it
      if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) {
        return false;
      }
      stack.pop(); // matched, so this pair is done
    }
  }
  return stack.length === 0; // anything left open means invalid
}

console.log(isValid("()")); // Output: true
console.log(isValid("()[]{}")); // Output: true
console.log(isValid("{[()]}")); // Output: true
console.log(isValid("(]")); // Output: false
console.log(isValid("([)]")); // Output: false
console.log(isValid("((")); // Output: false
console.log(isValid("))")); // Output: false
console.log(isValid("")); // Output: true

Trace for {[()]}:

• { push → stack {
• [ push → stack { [
• ( push → stack { [ (
• ) top is (, match, pop → stack { [
• ] top is [, match, pop → stack {
• } top is {, match, pop → stack empty → true

Trace for ([)]: after ( and [, the ) arrives but the top is [, so we return false immediately.

There are exactly three ways a bracket string can be invalid, and the code catches each one:

1. A closing bracket with nothing open (like ))): the stack is empty when we try to match.
2. A closing bracket of the wrong type (like (] or ([)]): the top of the stack is a different opening bracket.
3. Opening brackets never closed (like ((): the loop finishes but the stack is not empty.

The map from closing to opening bracket keeps the check to one line and makes it easy to add new pairs, such as < and >.

With only one type of bracket, ( and ), a single counter is enough: add 1 for (, subtract 1 for ), fail if it ever goes negative, and check it ends at 0. With several types a counter cannot tell that ([)] is wrong, so you need the stack.

• Returning true as soon as the loop ends, without checking that the stack is empty.
• Reading or popping from an empty stack. In JavaScript that silently gives undefined; in Java it throws an exception.
• Using separate counters for each bracket type. Counts for ([)] balance perfectly, yet the string is invalid.
• An odd-length string can never be valid. That is a fine quick check, but not a replacement for the stack.

• How would you find the length of the longest valid parentheses substring?
• What is the minimum number of brackets to add to make a string valid?
• How would you generate all valid combinations of n pairs of parentheses?
• Where are stacks used in real software? (Undo, browser back button, function calls, expression parsing.)