Bracket Match — Stack and Hash Map

We are going to make an algorithm that can identify from a text that only includes the characters “(){}[]” if its content is well formed, that is, a bracket match.

Just to be clear, the string will never come empty or with characters different than those mentioned above.

Example of a string with Bracket Match.
“(([{[()]}]))”

Example of a string without Bracket Match.
“){}”
“[{(})]”

The first thing I did was create a stack where I’m going to add one by one the characters that the string S has (S is called the String).

In second step created a Hash Map where the keys are the opening brackets and their respective values ​​are the closing brackets, this will allow me to do searches in constant time, look like this:

hash-map = {
‘(‘ = ‘)’,
‘{‘ = ‘}’,
‘[‘ = ‘]’,
}

To understand the following steps, it’s necessary to know at least 3 main methods that the stack structure has, which are Push, Peek and Pop.

The load management of a stack is L.I.F.O. (Last In First Out)

Now I can enter to evaluate all the content of “S”.

Then… Each character may have the only characteristics that are opened or closed.

When it’s opened, I’ll do a .push() to the stack.

When it’s closed, I’ll do two more evaluations to be sure what should I do with the character.

1. At this point I know that I am evaluating a closed character, therefore, I will try to make a match with the last element that is on the stack, if when doing a .peek() the result is null, it means that there is nothing in the stack. stack and string S is badly formed, return false.
2. For this second condition I will need two elements to compare, 1. The character that comes from the string “S” and 2. Extract the top of the stack and pass it as an argument of type key and obtain the respective value. If these two values are equal that means they matched, therefore, I do a .pop() to remove the opening bracket from the stack.

Finally, I make a statement, that is, I’m going to return the result of the statement (stack.size () == 0) what I mean by the statement is that if it’s true is because all the brackets matched and if the statement is false means that the string is badly formed.

Personal note