JavaScript program to Check the Expression has valid or Balanced Parenthesis or Not
Given the expression string, Our task is to Check whether the expression has valid or Balanced parenthesis or not in JavaScript. Valid input refers to every bracket having its corresponding bracket of the same type in the correct order.
Example:
Input: exp = "[()][()()]()"
Output: True.
Explanation: All of the brackets are balanced.
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 Stack
- Using JavaScript Regular Expression
- Using Counter Method
Using Stack
Initializing an empty stack and iterating through each character in the expression, pushing opening parentheses onto the stack. When encountering a closing parenthesis, it checks if it matches the last open parenthesis on the stack; if not, it returns false otherwise, it removes the last parenthesis from the stack. Finally, if the stack is empty at the end, it returns true otherwise, returns false.
Example: The example below shows how to Check the expression has valid or Balanced parenthesis or not in JavaScript Using Stack.
function validParenthesis(x) {
let stack = [], i = 0;
while (i < x.length) {
// If bracket is open then push it into stack
if (x[i] == '(' || x[i]
== '{' || x[i] == '[')
stack.push(x[i]);
else {
// Checking right corresponding bracket
if (x[i] == ')' && stack[stack.length - 1] != '(')
return false;
if (x[i] == ']' && stack[stack.length - 1] != '[')
return false;
if (x[i] == '}' && stack[stack.length - 1] != '{')
return false;
stack.pop();
}
i++;
}
if (stack.length)
return false;
return true;
}
console.log(validParenthesis('{[[]()]}'));
Output
true
Time complexity: O(n), Because we iterate through the given expression one time.
Space complexity: O(n), Because we use a stack of size ‘n’ to store open bracket ( ‘(‘, ‘[‘, ‘{‘).
Using Regular Expression
This method utilizes regular expressions to remove all characters from the expression except parentheses. Then, it repeatedly replaces pairs of matching parentheses until none are left. Empty string means that expression is balanced otherwise not.
Example: The example below shows how to Check the expression has valid or Balanced parenthesis or not using Regular Expression.
function validParenthesis(expression) {
const regex = /[^(){}\[\]]/g;
expression = expression.replace(regex, '');
const pair = /(\(\)|\{\}|\[\])/g;
while (pair.test(expression)) {
expression = expression.replace(pair, '');
}
return expression.length === 0;
}
console.log(validParenthesis("({}[])"));
console.log(validParenthesis("((}"));
Output
true false
Time complexity: O(n2)
Space complexity: O(1)
Using Counter Method
In this approach, we increment count if open bracket comes and decrement count if close bracket comes for different brackets counter variable is different. At the end, if all counter values are zero then return true otherwise return false.
Example: The example below shows how to Check the expression has valid or Balanced parenthesis or not in JavaScript Using Counter Method.
function validParenthesis(str) {
let roundBracketCount = 0,
squareBracketCount = 0,
curlyBracketCount = 0;
for (let i = 0; i < str.length; i++) {
if (str[i] == '(') roundBracketCount++;
else if (str[i] == ')') roundBracketCount--;
else if (str[i] == '[') squareBracketCount++;
else if (str[i] == ']') squareBracketCount--;
else if (str[i] == '{') curlyBracketCount++;
else if (str[i] == '}') curlyBracketCount--;
}
return (roundBracketCount === 0 &&
squareBracketCount === 0 &&
curlyBracketCount === 0);
}
console.log(validParenthesis("(([]))"));
console.log(validParenthesis("[]{()}"));
Output
true true
Time complexity: O(n)
Space complexity: O(1)
Contact Us