How to use Stack In Javascript
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 ( ‘(‘, ‘[‘, ‘{‘).
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
Contact Us