Posted on

Balanced Brackets (Interview Question) in C++

So the question essentially asks you to write a boolean function that returns true if the input string is “balanced.” Balancing simply means that each open bracket has a closed bracket. You’re given a string like this: 

string inString = "{[()]}";

In this example, this is a “balanced” string, because each opening bracket must have a closed bracket. 

string inString = "[(])";

Now this one is not balanced. Why? Because it has overlapping brackets. Think of it like a venn diagram

Venn Diagram Maker | Lucidchart

Nothing can be in the center. So the question is, how do we implement this algorithm? This is my solution:

using namespace std;
#include <stack>
#include <vector>
#include <map>

bool IsOpenBracket(char InCharacter)
{
	vector<char> openCharacters = { '{', '(', '[' };
	if (count(openCharacters.begin(), openCharacters.end(), InCharacter))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool IsClosedBracket(char InCharacter)
{
	vector<char> closedCharacters = {'}', ')', ']'};
	if (count(closedCharacters.begin(), closedCharacters.end(), InCharacter))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool balancedBrackets(string str) {
    stack<char> s;
    map<char, char> matching_brackets =
		{
			{'}', '{'},
			{')', '('},
			{']', '['}
		};

    for (int i = 0; i < str.size(); i++)
    {
        char currentCharacter = str[i];
        if (IsOpenBracket(currentCharacter))
        {
            s.push(currentCharacter);
        }
        else if (IsClosedBracket(currentCharacter))
        {
            if (s.size() == 0)
            {
                return false;
            }
            
					  if(s.top() == matching_brackets[currentCharacter])
            {
                s.pop();
            }
            else
            {
                return false;
            }
        }
    }

    if (s.size() == 0)
    {
        return true;
    }
    
    return false;
}

In my code I essentially start out by making two boolean methods for readability. One is called “IsOpenBracket” and the other is called “IsClosedBracket” both of these functions take in a character and then return true or false if they are an open or closed bracket respectively.

After this is our “balancedBrackets” method which takes in a string. At the beginning of the method, I define a stack of characters called “s”

After this I define a map called matching_brackets which essentially is used later to give us the opposite bracket of what we turn in. So if you pass in ‘)’ it gives you ‘(‘

The next step is to essentially loop through each character in the string one by one and then I define a character called currentCharacter, which I set as a local temp variable for each loop iteration.

The first step now is to essentially check if this currentCharacter is an open bracket or a closed bracket. If it’s an open bracket, we just push it to the stack. Why? Because at the end of our function, we will check to see if there is anything in the stack. If the stack is empty, we return true, if it’s not empty, we return false. The whole premise of this method is that we push when it’s an open character, and pop when it’s a matching closing character.

Alright so, if it’s not an open bracket, we then check to see if the size of the stack is 0. We do this because if the stack is empty and we are inside of the “IsClosedBracket” part of the if statement, then we essentially are adding a closed bracket because we have an open bracket, which would be an immediate failure case.

After this we essentially check if the top of the stack is equal to the opposite of our current closing bracket. This is essentially the main trick. Remember the map that was made earlier? This is why it was made. So essentially, because a stack is last in, first out, the top of the stack is essentially the last open bracket we pushed, and we are checking if the top of that stack is equal to the opposite of our current closing bracket.

The last part is that we return false. Why do we return false here? This is because if we are on a closing bracket, and the current top is not equal to the opposite of our closing bracket, then we are overlapping. This would not follow the rules, so we would return false.

Lastly, we just check if the current size is 0, which means we popped off all of the opening brackets, meaning there is no open bracket without a matching closing bracket. If it’s not zero, we just return false as to say that the string is not balanced.

If you want to read the entire rules of this algorithm, you can read it here on hackerrank: https://www.hackerrank.com/challenges/balanced-brackets/editorial

Posted on

Breadth First Search

This is similar to what I was doing when I was researching DFS (Depth First Search), which you can see below here I posted a link to my other posting.

Implementing DFS (Depth First Search) in C++

Alright so hopefully the DFS algorithm makes sense. It’s very simple once you got it. Once you got it, you got it!

Breadth First Search is a little bit trickier, but don’t worry. It’s still easy to learn. For BFS, it might be implemented like this:

vector<string> breadthFirstSearch(vector<string> *array) {
    queue<Node*> q;
		array->push_back(name);
		q.push(this);
		
		while (!q.empty())
		{
			Node* n = q.front();
			q.pop();
			
			for (int i = 0; i < n->children.size(); i++)
			{
				if (count(array->begin(), array->end(), n->children[i]->name) == 0)
				{
					array->push_back(n->children[i]->name);
					q.push(n->children[i]);
				}
			}
		}
			
    return *array;
  }

In the above sample, this method will essentially print out all of the children of a graph in breadth first search. That is, level by level. However, in a real situation, you would simply return the node when you find what you are looking for.