In this assignment, you will apply what we've learned so far in this lesson to solve the "Matching Brackets" problem. First, identify which data structure could help you solve this problem. Feel free to use an array either as a stack or a queue, depending on what you find most suitable.
Make sure to apply the PEDAC process. In this challenge, it's important to understand the problem well and break down the logical rules of matching brackets to be able to apply these rules to a solution.
// Write a function `areMatched` that takes a string as an argument
// and returns true if all types of brackets (parentheses (),
// square brackets [], and curly braces {}) in the string are
// properly matched. For the brackets to be considered
// matched, every opening bracket must have a corresponding
// closing bracket of the same type, and the brackets must be
// correctly nested.
console.log(areMatched("()")); // Output: true
console.log(areMatched("([()]{})")); // Output: true
console.log(areMatched("([((}]({}))")); // Output: false
console.log(areMatched("{{[[(())]]}}")); // Output: true
console.log(areMatched("")); // Output: true
console.log(areMatched("([)]")); // Output: false
You can use a Stack data structure to solve this problem.
For this problem, we'll maintain a stack as we iterate through the characters of the input string.
There are two distinct cases to consider based on the character type:
(
, [
, {
), we push it onto the stack.
)
, ]
, }
):
false
immediately.
false
.
false
, we can continue iterating.
At the end of the process, if the stack is empty, all brackets are properly matched, and we can return true
. Otherwise, if any brackets remain unmatched in the stack, we return false
.
Let's do a detailed walkthrough using a string "([()]{})"
.
Step 1: The first character is an open bracket, so we push it to the stack.
Step 2: Once again, the character is an open bracket, so we push it to the stack.
Step 3: In the third step we encounter an open bracket yet again.
Step 4: In the fourth step, the character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.
Step 5: Once again, the character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.
Step 6: The character is an open bracket, so we push it to the stack.
Step 7: The character is a closed bracket so we pop the last character from the stack and check if it matches the current character. Since the characters match, we continue.
Step 8: Finally, the last character is a closed bracket so we pop the last character from the stack and check if it matches the current character. The characters match, so we continue.
Step 9: We've reached the end of the string. We now check to see if the stack is empty. Since it is, we return true
.
In the walkthrough, we've seen an example where all brackets matched correctly and the stack was empty at the end. Now, let's visually explore cases where this might not be true, and we'd have to return false
instead.
In this example, we would push the open bracket to the stack and successfully completed our iterations. At the end, however, our stack is not empty and we return false
.
Here, we encounter a closing bracket. That means we want to pop from the stack to compare with our closing bracket. In this case, the stack is empty, meaning we have a closing bracket with no matching opening bracket and we return false
.
In the above example, we try to pop from an empty stack on the first iteration, but this isn't necessarily always the case. Consider what happens with the string '{()}]'
.
In our first step, we would push our first opening bracket onto the stack.
In the second step, we encounter a closing bracket. We successfully pop from the stack to get a character to compare against our bracket. When we make the comparison, however, they are not compatible brackets and we return false
.
In our implementation we'll use an array as a stack.
function areMatched(string) {
const stack = [];
const matches = {
'(': ')',
'[': ']',
'{': '}',
};
for (let char of string) {
if (['(', '[', '{'].includes(char)) {
stack.push(char);
} else if ([')', ']', '}'].includes(char)) {
if (stack.length === 0 || matches[stack.pop()] !== char) {
return false;
}
}
}
return stack.length === 0;
}
console.log(areMatched("()")); // Output: true
console.log(areMatched("([()]{})")); // Output: true
console.log(areMatched("([((}]({}))")); // Output: false
console.log(areMatched("{{[[(())]]}}")); // Output: true
console.log(areMatched("")); // Output: true
console.log(areMatched("([)]")); // Output: false