BracketMatcher.md

Bracket Matcher

Ever wonder how your linter knows if you have matching brackets? Well it's time to think of a solution to that!

Given a set of brackets, [, {, (, create a function that determines if the brackets are well-formed (match) or not - even with bracket nesting. For example:

bracket('{}');

// => true

bracket('{(');

// => false

bracket('{()}');

// => true

bracket('{[)][]}');

// => false

bracket(']');

// => false

bracket('({[]}{[]})');

// => true

Instructions

1. Copy this markdown and paste in your own, private gist
2. In your private gist, fill out the questions below
3. Submit by the due time as instructed in Zoom

Rewrite the question in your own words:

• Given a string of 'brackets', check to see if each set of brackets has both an opening and closing bracket.

What assumptions will you make about this problem if you cannot ask any more clarifying questions? What are your reasons for making those assumptions?

• The input will always be a string containing ONLY brackets and not other characters such as numbers and letters.
• I assume this because I do not think they are testing my error handling in this problem.
• The output should be a boolean.

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

• Closing bracket occurs BEFORE a an opening bracket. FALSE
• If two types of opening brackets, expect the latter to close first. TRUE
• If only an opening bracket occurs without a closing bracket. FALSE

How would you identify the elements of this problem?

• Searching of Data
• Sorting of Data
• Pattern Recognition
• Build/Navigate a Grid
• Math
• Language API knowledge
• Optimization

Which data structure(s) do you think you'll use? What pros/cons do you see with that choice?

• String into array
• CON: have to use extra function. PRO: can iterate over an array and not a string.

Write out a few lines of initial pseudocode: (mid-level design, NOT REAL CODE)

• Brake the initial STRING into an array.
• For each element in the array, check if it is an opening or closing bracket.
• If it is an closing bracket, and the opening bracket has NOT occurred yet STOP.
• If it is an opening bracket, check if the closing bracket occurs. If not STOP.
• If both the opening and closing bracket occur, and in that order, is there anything between them?
• If there IS something between them, check if the next character is an opening bracket that matches the penultimate character.
• Continue in this pattern until you have confirmed that ALL opening brackets have the necessary closing bracket.

Write out any implementation code OR link to repl

What is the Big O complexity of your solution?