VietMX Staff asked 3 years ago
One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched.
Here are some of the balanced and unbalanced expressions:
Algorithm
- Declare a character stack which will hold an array of all the opening parenthesis.
- Now traverse the expression string exp.
- If the current character is a starting bracket (
(or{or[) then push it to stack. - If the current character is a closing bracket (
)or}or]) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced. - After complete traversal, if there is some starting bracket left in stack then “not balanced”
Complexity Analysis
- We are traversing through each character of string, Time complexity
O(n). - We are storing the opposite parentheses characters in the stack, in the worst case there can be all the opposite characters in the string, Space complexity
O(n).
Implementation
let isMatchingBrackets = function (str) { let stack = []; let map = { '(': ')', '[': ']', '{': '}' } for (let i = 0; i < str.length; i++) { // If character is an opening brace add it to a stack if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) { stack.push(str[i]); } // If that character is a closing brace, pop from the stack, which will also reduce the length of the stack each time a closing bracket is encountered. else { let last = stack.pop(); //If the popped element from the stack, which is the last opening brace doesn’t match the corresponding closing brace in the map, then return false if (str[i] !== map[last]) {return false}; } } // By the completion of the for loop after checking all the brackets of the str, at the end, if the stack is not empty then fail if (stack.length !== 0) {return false}; return true;}