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
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.