JavaScript Program to Check Valid Parentheses Using String
In this article, we will learn how we can check valid parentheses of a string, and write a program to check whether the pairs and order of “{ “, ” } “, “(“, “)”, “[“, “]” in the string expression is right or not.
Example:
Input: exp = "[()][()()]()"
Output: True.
Explanation: all of the brackets are properly formed.
Input: exp = "[(])"
Output: False
Explanation: The first and fourth brackets are not balanced because there is a closing ']' before the final '('.
Table of Content
- Using the Stack
- Using Counter
- Using Regular Expression
- Using a Map for Character Matching
- Using a recursive function:
Using the Stack
This method involves using a stack data structure to keep track of parentheses and ensuring they are properly closed.
- Begin by initializing a stack.
- Iterate, through the given string.
- If an open parenthesis is encountered, push it onto the stack.
- If a closing parenthesis is encountered check if it matches the element of the stack.
- If they match, pop the element from the stack; otherwise conclude that the parentheses are not balanced and return false.
- After iterating through all characters in the string if the stack is empty it means all parentheses have been correctly closed so return true.
Syntax:
stackname.push(value);
stackname.pop()
function isValidParentheses(str) {
const stack = [];
const pairs = {
"(": ")",
"[": "]",
"{": "}",
};
for (let char of str) {
if (pairs[char]) {
stack.push(char);
} else if (
char === ")" ||
char === "]" ||
char === "}"
) {
if (
pairs[stack.pop()] !==
char
) {
return false;
}
}
}
return stack.length === 0;
}
const inputString = "({()})";
console.log(
`Is it a valid Paranthesis ? :
${isValidParentheses(inputString)}`
);
Output
Is it a valid Paranthesis ? : true
Using Counter
This approach relies on using a counter to keep track of the balance between closing parentheses.
- Start by initializing a counter variable.
- Iterate through each character in the given string.
- Increment the counter whenever an open parenthesis is encountered and decrement it for each closing parenthesis found.
- If at any point during iteration the counter becomes negative it implies that there are closing parentheses than opening ones; thus return false.
- Once finished iterating through all characters in the string if the counter equals zero it indicates that all parentheses have been properly balanced, hence return true.
Syntax:
for ( variable of iterableObjectName) {
...
}
function isValidParentheses(str) {
let count = 0;
for (let char of str) {
if (char === "(") {
count++;
} else if (char === ")") {
if (count === 0) {
return false;
}
count--;
}
}
return count === 0;
}
const inputString = "((()))";
console.log(
`Is it a valid Paranthesis ? :
${isValidParentheses(inputString)}`
);
Output
Is it a valid Paranthesis ? : true
Using Regular Expression
In this method we employ expressions to repeatedly remove valid pairs of parentheses until none remain.
- Define an expression pattern that matches pairs of parentheses.
- Enter into a loop that finds and removes pairs using replace operations with a string as replacement text.
- Repeat step 2 until no valid pairs can be found in iterations (i.e. after performing replacements without finding any matches).
- If, after completing these iterations our initial string becomes empty it means all parentheses have been successfully matched and eliminated; thus return true. Otherwise return false.
Syntax:
/pattern/modifiers;
function isValidParentheses(str) {
const regex = /(\(\)|\[\]|\{\})/g;
while (str.match(regex)) {
str = str.replace(regex, "");
}
return str.length === 0;
}
const inputString = "{[()]]}";
console.log(
`Is it a valid Paranthesis ?
${isValidParentheses(inputString)}`
);
Output
Is it a valid Paranthesis ? false
Using a Map for Character Matching
This method uses a stack and a Map to match opening and closing brackets. As characters are processed, opening brackets are pushed onto the stack. When a closing bracket is encountered, it is checked against the stack’s top. The string is valid if the stack is empty.
Example: In this example The function isValidParentheses checks if a given string of parentheses is valid. It utilizes a stack and a map to match opening and closing parentheses. The examples demonstrate its correctness.
function isValidParentheses(s) {
const stack = [];
const matchingBrackets = new Map([
['(', ')'],
['{', '}'],
['[', ']']
]);
for (let char of s) {
if (matchingBrackets.has(char)) {
stack.push(char);
} else {
if (stack.length === 0 || matchingBrackets.get(stack.pop()) !== char) {
return false;
}
}
}
return stack.length === 0;
}
console.log(isValidParentheses("(){}[]"));
console.log(isValidParentheses("([{}])"));
console.log(isValidParentheses("(]"));
Output
true true false
Using a recursive function
This approach recursively removes pairs of matching parentheses until either all parentheses are balanced or an imbalance is detected. It continues this process until the string is empty or an imbalance is found, returning true if the parentheses are balanced and false otherwise.
function isValidParentheses(str) {
// Recursive function to check the balance of parentheses
const checkBalance = (s) => {
// Base case: empty string
if (s.length === 0) return true;
// Find the index of the first closing parenthesis
const closingIndex = s.indexOf(')');
if (closingIndex === -1) return false; // If no closing parenthesis is found, parentheses are unbalanced
// Find the index of the nearest opening parenthesis before the closing parenthesis
const openingIndex = s.lastIndexOf('(', closingIndex);
if (openingIndex === -1) return false; // If no opening parenthesis is found, parentheses are unbalanced
// Remove the matched parentheses and continue checking the balance
const remaining = s.slice(0, openingIndex) + s.slice(openingIndex + 1, closingIndex) + s.slice(closingIndex + 1);
return checkBalance(remaining);
};
// Call the recursive function
return checkBalance(str);
}
const inputString = "({()})";
console.log(`Is it a valid Paranthesis ? : ${isValidParentheses(inputString)}`);
Output
Is it a valid Paranthesis ? : false