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
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()
Javascript
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) {
...
}
Javascript
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;
Javascript
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
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
