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.

Comments

Please log in to post a comment.

No comments yet.

Be the first to comment!