es404020

Posted on Jun 23

Bracket Matching / Valid Parentheses

Bracket matching is a common problem in programming interviews and coding challenges. The goal is to determine whether a given string made up of brackets is balanced and properly nested.

Typical brackets to validate include:

Parentheses: ()
Square brackets: []
Curly braces: {}

Problem Statement

Given a string containing only the characters (, ), {, }, [ and ], write a function to determine if the input string is valid.

A string is considered valid if:

Open brackets are closed by the same type of brackets.
Open brackets are closed in the correct order.
Every closing bracket has a corresponding opening bracket of the same type.

Original JavaScript Implementation

const bracket = (value) => {
  let array = value.split(""); // Convert input string into an array of characters
  let stack = [];               // Stack to hold opening brackets
  let stack_close = [];         // Stack to hold unmatched closing brackets (not necessary)
  let i = 0;

  // If the total number of brackets is odd, it's automatically invalid
  if (array.length % 2 != 0) {
    return false;
  }

  // Loop through each character
  while (array.length > i) {
    if (array[i].includes('(') || array[i].includes('[') || array[i].includes('{')) {
      stack.push(array[i]); // Push opening bracket to the stack
    } else {
      stack_close.push(array[i]); // Push closing bracket to the close stack

      console.log(stack[stack.length - 1], array[i]); // Debug log

      // Check for matching bracket pairs
      if (array[i].includes(']') && stack[stack.length - 1] == '[') {
        stack.pop();
        stack_close.pop();
      } else if (array[i].includes(')') && stack[stack.length - 1] == '(') {
        stack.pop();
        stack_close.pop();
      } else if (array[i].includes('}') && stack[stack.length - 1] == '{') {
        stack.pop();
        stack_close.pop();
      }
    }
    i++;
  }

  // If both stacks are empty, the brackets are properly matched
  if (stack.length == 0 && stack_close.length == 0) {
    return true;
  } else {
    return false;
  }
}

Explanation Line-by-Line

const bracket = (value) => {

Defines a function named bracket that takes a string input value.

let array = value.split("");

Splits the string into an array of characters to process them individually.

let stack = [];
let stack_close = [];

Two stacks are initialized: one for opening brackets and one for closing brackets. Only stack is actually necessary.

let i = 0;

Index i initialized to loop through the array.

if (array.length % 2 != 0) {
  return false;
}

If the length of the array is odd, it can’t be balanced, so return false early.

while (array.length > i) {

Starts a while loop to iterate through the array.

  if (array[i].includes('(') || array[i].includes('[') || array[i].includes('{')) {
    stack.push(array[i]);
  }

Checks if the current character is an opening bracket and pushes it onto the stack.

  else {
    stack_close.push(array[i]);

If it’s a closing bracket, push it to the close stack (this step is not needed for logic).

    console.log(stack[stack.length - 1], array[i]);

Debug print of the last opened bracket and the current closing bracket.

    if (array[i].includes(']') && stack[stack.length - 1] == '[') {
      stack.pop();
      stack_close.pop();
    } else if (array[i].includes(')') && stack[stack.length - 1] == '(') {
      stack.pop();
      stack_close.pop();
    } else if (array[i].includes('}') && stack[stack.length - 1] == '{') {
      stack.pop();
      stack_close.pop();
    }
  }

Checks if the current closing bracket matches the last opening bracket. If yes, both are removed from their stacks.

  i++;
}

Increment index and continue loop.

if (stack.length == 0 && stack_close.length == 0) {
  return true;
} else {
  return false;
}

At the end, if both stacks are empty, the brackets were all properly matched and nested.

Example Usages

bracket("{[()]}"); // true
bracket("([)]");   // false
bracket("([]{})"); // true
bracket("((" );    // false

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because of the stack usage.

Conclusion

This custom bracket validation implementation uses two stacks and performs step-by-step matching of brackets. While effective, it can be simplified by using only one stack for better efficiency and readability.

DEV Community