Stacks in JS and Parenthesis Matching
Stacks are a useful data structure that holds a list of elements. A stack works in a “last in”, “first out” principle meaning that the most recently added element is the first one to remove. The stack has two main methods that we use, .push() and .pop().
const reverse = (str) => {
let stack = []; // push letter into stack for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
// pop letter from the stack let reverseStr = ''; while (stack.length > 0) {
reverseStr += stack.pop();
}
return reverseStr;
} console.log(reverse('JavaScript Stack')); //kcatS tpircSavaJ
Explanation of the code above:
The reverse function takes in a string as an argument and returns it in reverse order through the following logic. First, we loop through the string and push each element into a stack we create. Lastly, we create an empty string and pop the elements of the stack into our string, and return it.
There are many applications of the use of stacks, such as reversing a string. The solution is to push each letter into the stack and then pop them back off. More examples of the stack applications are the “undo” mechanism in text editors, syntax parsing, function call, and expression conversion.
But I came across the need for a stack when trying to solve the problem of parenthesis matching. The problem is checking for a balanced number of MATCHING parenthesis or brackets i.e. “ (, ), [, ], {, }” and if not then how many and which should be added. For example, the function should return true for “{[(}])” and false for “{[)]” or “)(“.
The algorithm is as follows first we declare a variable stack as an empty array. Then, traverse the input string expression. 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 the stack and if the popped character is the matching starting bracket then we can continue, else the parenthesis is not balanced. After complete traversal, if there is some starting bracket left in the stack then “not balanced”.
const isMatchingBrackets = (str) => {
let stack = [];
let map = {
'(': ')',
'[': ']',
'{': '}'
}
for (let i = 0; i < str.length; i++) {
if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) { stack.push(str[i]);
} else {
let last = stack.pop();
if (str[i] !== map[last]) {return false};
}
}
if (stack.length !== 0) {return false};
return true;
} console.log(isMatchingBrackets("(){}")); // returns true
console.log(isMatchingBrackets("[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]")); // returns trueconsole.log(isMatchingBrackets("({(()))}}")); // returns false
Resources: https://www.javascripttutorial.net/javascript-stack/
