One of my former colleagues has asked  me if I can solve the problem described in the following blog post:

http://www.dev102.com/2008/07/21/a-programming-job-interview-challenge-13-brackets/

The problem short:

“Your input is a string which is composed from bracket characters. The allowed characters are:’(‘, ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

Example of a legal expression: “([](<{}>))”.

Example of an illegal expression: “({<)>}”.

Provide the most efficient, elegant and simple solution for that problem.I think that this is a well known problem but I am not sure, so excuse me if this week’s question is screwed.”

Well knowing that I am always up to this kind of challenges here is my solution:

[code lang="java"]
package test;

import java.util.Stack;

/**
* Brakets problem implementation:
*

* Your input is a string which is composed from bracket characters. The allowed
* characters are:’(', ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to
* determine whether the brackets structure is legal or not.
*
* Example of a legal expression: “([](<{}>))”.
*
* Example of an illegal expression: “({<)>}”.
*
* Provide the most efficient, elegant and simple solution for that problem.I
* think that this is a well known problem but I am not sure, so excuse me if
* this week’s question is screwed.
*

*
* @author Norbert Rakosi
*/
public class Brakets {

/**
* Main method
*
* @param args
*/
public static void main(String[] args) {
System.out.println(checkBrackets("([](<{}>))"));
System.out.println(checkBrackets("({<)>}"));
System.out.println(checkBrackets(")({<)>}"));
}

/**
* Called to check if the given string is a valid bracket string.
*
* Example of a legal expression: “([](<{}>))”.
*
* Example of an illegal expression: “({<)>}”.
*
* @param string
* @return
*/
public static boolean checkBrackets(String string) {
boolean ret = true;
final Stack stack = new Stack();
for (int i = 0; i < string.length() && ret; i++) {
final char chr = string.charAt(i);
int offset = 0;
switch (chr) {
case '(':
case '{':
case '[':
case '<': {
// add the open bracket to stack
stack.push(chr);
break;
}
/*
* We take advantage of the fact that
* '{' - '}' = 2
* '[' - ']' = 2
* '<' - '>' = 2
* '(' - ')' = 1
* we build up the offset
* */
case '}':
case ']':
case '>':
offset++;
case ')': {
offset++;
ret = ((stack.size() > 0) && ((Character) stack.pop() == (chr - offset)));
break;
}
default:
break;
}
}

//the stack should be empty
ret &= (stack.size() == 0);

return ret;
}
}
[/code]

Thanks  George for the challenge.

Happy coding