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:

  1. package test;
  2.  
  3. import java.util.Stack;
  4.  
  5. /**
  6. * Brakets problem implementation:
  7. * <p>
  8. * Your input is a string which is composed from bracket characters. The allowed
  9. * characters are:’(’, ‘)’, ‘[’. ‘]‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to
  10. * determine whether the brackets structure is legal or not.
  11. *
  12. * Example of a legal expression: “([](<{}>))”.
  13. *
  14. * Example of an illegal expression: “({<)>}”.
  15. *
  16. * Provide the most efficient, elegant and simple solution for that problem.I
  17. * think that this is a well known problem but I am not sure, so excuse me if
  18. * this week’s question is screwed.
  19. * </p>
  20. *
  21. * @author Norbert Rakosi
  22. */
  23. public class Brakets {
  24.  
  25.     /**
  26.      * Main method
  27.      *
  28.      * @param args
  29.      */
  30.     public static void main(String[] args) {
  31.         System.out.println(checkBrackets(“([](<{}>))”));
  32.         System.out.println(checkBrackets(“({<)>}”));
  33.         System.out.println(checkBrackets(“)({<)>}”));
  34.     }
  35.  
  36.     /**
  37.      * Called to check if the given string is a valid bracket string.
  38.      *
  39.      * Example of a legal expression: “([](<{}>))”.
  40.      *
  41.      * Example of an illegal expression: “({<)>}”.
  42.      *
  43.      * @param string
  44.      * @return
  45.      */
  46.     public static boolean checkBrackets(String string) {
  47.         boolean ret = true;
  48.         final Stack stack = new Stack();
  49.         for (int i = 0; i < string.length() && ret; i++) {
  50.             final char chr = string.charAt(i);
  51.             int offset = 0;
  52.             switch (chr) {
  53.             case ‘(’:
  54.             case ‘{’:
  55.             case ‘[’:
  56.             case ‘<’: {
  57.                 // add the open bracket to stack
  58.                 stack.push(chr);
  59.                 break;
  60.             }
  61.             /*
  62.              * We take advantage of the fact that
  63.              * ‘{’ - ‘}’ = 2
  64.              * ‘[’ - ‘]’ = 2
  65.              * ‘<’ - ‘>’ = 2
  66.              * ‘(’ - ‘)’ = 1
  67.              * we build up the offset
  68.              * */
  69.             case ‘}’:
  70.             case ‘]’:
  71.             case ‘>’:
  72.                 offset++;
  73.             case ‘)’: {
  74.                 offset++;
  75.                 ret = ((stack.size() > 0) && ((Character) stack.pop() == (chr - offset)));
  76.                 break;
  77.             }
  78.             default:
  79.                 break;
  80.             }
  81.         }
  82.        
  83.         //the stack should be empty
  84.         ret &= (stack.size() == 0);
  85.        
  86.         return ret;
  87.     }
  88. }

Thanks  George for the challenge.

Happy coding