GAZAR

Principal Engineer | Mentor

Valid Parentheses Algorithm

Valid Parentheses Algorithm

At its core, the Valid Parentheses algorithm verifies whether the arrangement of parentheses in a given string is valid. For a string to be considered valid, each opening parenthesis must have a corresponding closing parenthesis, and they must be properly nested within each other. Common types of parentheses include round brackets (), square brackets [], and curly braces {}.

Initialize an empty stack to store opening parentheses encountered during traversal.

  • Iterate through each character in the input string.
  • If the character is an opening parenthesis (i.e., '(', '[', or '{'), push it onto the stack.
  • If the character is a closing parenthesis (i.e., ')', ']', or '}'), check if the stack is empty:
  • If the stack is empty, return false, indicating an unbalanced parentheses sequence.
  • Otherwise, pop the top element from the stack and compare it with the current closing parenthesis. If they do not match, return false.
  • After iterating through all characters, if the stack is empty, return true (indicating a valid parentheses sequence); otherwise, return false.

Let's implement this algorithm in JavaScript:

const parenthesesMap = {
  '(':')',
  '[':']',
  '{':'}'
}

function isValid(text) {
  const foundStack = [];
  for (let i = 0 ; i < text.length ; i+=1 ) {
      const foundOpenParenthese = Object.keys(parenthesesMap).find(item => item === text[i])
      if (foundOpenParenthese){
          foundStack.push(foundOpenParenthese)
      } else {
          const foundCloseParenthese = Object.values(parenthesesMap).find(item => item === text[i])
          if (foundCloseParenthese) {
             const lastItem = parenthesesMap[foundStack.pop()];
               if (lastItem !== text[i]) {
                   return false
               }
          }
      }
  }
  return foundStack.length === 0
}


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

Screenshot 2024-03-10 at 3.38.53 PM.png

Conclusion:

So, whether you're parsing code syntax or validating mathematical expressions, embrace the Valid Parentheses algorithm and let its power guide your journey through the world of JavaScript programming.