It is pitch dark in the Twin Cities of Minneapolis and St. Paul. Before calling it a day I decided to try one more practice problem from the Facebook web site. Balance Brackets is a very common problem. In general the idea is that you are given a set of brackets and are sked to determine if the brackets are balanced.
I knew I have solved similar versions of the problem. When done with the code I move to a different computer and type in the contents for the post. I looked up in my web site for the string “balanced brackets” and found Balanced Brackets and Balanced Brackets – Possible Second Attempt. I generated the post in 2016 and 2017 respectively. I guess, we will have a third version.
I will solve the problem using the Java 8 programming language on a Windows 10 machine using the VSCode IDE. If you are planning on interviewing with Facebook I would suggest writing your code directly in the IDE presented by Facebook. Most (never generalize) IDEs have auto completion and when you decide to use a standard class the import is generated automatically. This is not the case with the Facebook IDE.
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].
We consider two brackets to be matching if the first element is an open-bracket, e.g., (, {, or [,
and the second bracket is a close-bracket of the same type,
e.g., ( and ), [ and ], and { and } are the only pairs of matching brackets.
Furthermore, a sequence of brackets is said to be balanced if the following conditions are met:
o The sequence is empty, or
o The sequence is composed of two, non-empty, sequences both of which are balanced, or
o The first and last brackets of the sequence are matching,
and the portion of the sequence without the first and last elements is balanced.
You are given a string of brackets.
Your task is to determine whether each sequence of brackets is balanced.
If a string is balanced, return true, otherwise, return false.
Not much to say. The requirements seem to be simple and quite clear.
boolean isBalanced(String s) {
}
This is the signature of the function we need to complete. We are presented with the input string and we need to return true if the brackets are balanced or false if not.
{[()]}
main <<< s ==>{[()]}<==
main <<< isBalanced: true
{}()
main <<< s ==>{}()<==
main <<< isBalanced: true
{(})
main <<< s ==>{(})<==
main <<< isBalanced: false
)
main <<< s ==>)<==
main <<< isBalanced: false
(
main <<< s ==>(<==
main <<< isBalanced: false
The requirements provide the first 4 examples. I added the fifth.
Since I solved the problem in my computer I needed a test scaffolding to accept a string, pass it to the function and display the results. The test scaffolding I wrote IS NOT PART OF THE SOLUTION.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read line ****
String s = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** process string and display result ****
System.out.println("main <<< isBalanced: " + isBalanced(s));
}
The idea is simple. We read in a string and display it to make sure all is well so far. We then call the function we need to complete and display the returned value.
/**
* If a string is balanced, return true, otherwise, return false.
* Runtime O(n)
*/
static boolean isBalanced(String s) {
// **** sanity check(s) ****
if (s.length() == 0)
return true;
if (s.length() == 1)
return false;
// **** initialization ****
Stack<Character> stack = new Stack<>();
// **** process the string one character at a time ****
for (char ch : s.toCharArray()) {
// **** closing bracket (pop from stack)****
if (ch == ')' || ch == ']' || ch == '}') {
// **** check if stack is empty ****
if (stack.isEmpty())
return false;
// **** pop top from stack (if matching) ****
if (ch == ')' && stack.peek() == '(')
stack.pop();
else if (ch == ']' && stack.peek() == '[')
stack.pop();
else if (ch == '}' && stack.peek() == '{')
stack.pop();
else
return false;
}
// **** opening bracket (push to stack) ****
else if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
}
// **** not a bracket ****
else {
System.out.println("isBalanced <<< unexpected ch: " + ch);
return false;
}
}
// **** check if stack is not empty ****
if (!stack.isEmpty())
return false;
// **** brackets are balanced ****
return true;
}
I like to start with sanity checks. They tend to speed up processing if you get a lot of noise. In this case we have two test cases. Not sure if it made much sense.
We will use a stack to keep track of the opening and closing brackets.
We loop through all the characters in the input string. We push an opening bracket, we pop from the stack a matching closing bracket, or we just exit if we get some other character.
For an opening bracket we just push it into the stack. For a closing bracket we first check if the stack is empty. If not we match the character at the top of the stack to match the current character.
There is one more thing we need to do after we exit the loop. We need to make sure the stack is empty. We could have received more opening brackets that closing ones. For this reason we need to check if the stack is not empty. This is why I added the last test case.
Please note that since the software had two test cases, my solution code might have issues. If you find a problem please leave me a message so I can address it.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,873 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com