Pass a comma separated string with brackets to a List

Issue

The method has to receive a String in format "[1,2,3,4,5]" with just integers inside, but it can also have "[1,2,3,[]]" or "[1,2,3,[1,2,3]]". I already have the code to just add the numbers to the list, but I can't figure out how to handle when I have another List inside.

I've thought of having a class List and when I find another brackets inside to call the function again, but don't know how to substring correctly when I see another opening bracket [. After I remove the brackets I split the string like this:

String[] arr = string.split(","); 

And start to add those results to the List I have to return with a for loop, my problem is when I see an opening bracket again [ I would have to substring and call with the resulting String my method again but don't know how to determine the closing bracket. What I've tried is to get the index of a closing bracket with indexOf:

String aux = arr[i];
int closingBracket = aux.indexOf("]");

But if I have an input string like [1,2,3,4,[,6] which shouldn't be accepted it will accept it.

Solution

What you need to do is figure out, on paper, what is called a finite state machine (FSM). When you encounter a token (comma, bracket, digit) you enter a particular state. Once in a certain state, you can only accept certain other tokens which may put you in a different state or leave you in the current one. You could have many different states which can accept different tokens and perform different actions.

For example.

When you see a digit, the next token may be.

 1.  Another digit
 2.  A closing bracket.
 3.  A comma.

Each of those tokens may prompt a different state and/or action.

 1. Another digit - keep on processing since numbers have many digits.
 2. closing bracket - save the number in a list and get the next list (See below)
 3. comma - save the number and look for next number

Assuming you want to save all of this in a list of lists it would be easiest to start off with a List<Object> since you can save integers and lists of lists in that type of list with indefinite depths.

I also suggest you look at the Stack class. You may want to be pushing the current list and popping a recent one as your parsing depth changes.

Finally, to ensure your brackets are properly matched to the following. Increment a counter when you see a '[' and decrement the counter when you see a ']'. If the counter ever goes negative, you have too many right brackets. If at the end it is positive, you don't have enough right brackets.

For more on this check out Finite State Machines at Wikipedia.

I decided to include a small example of what I was talking about. It may not cover all possible edge cases but the purpose is illustrative.

   public static void main(String[] args) {
      String strlist =
            "[1,2,113],     [4,5,[5,2,10],1], [],[1,2,3,4,5,[10,11,12,13,[14,15]]]";
      int bracketCount = 0;
      int num = 0;

      // inital list
      List<Object> list = new ArrayList<>();

      // hold sublists for precessing
      Stack<List<Object>> stack = new Stack<>();

      char[] chars = strlist.toCharArray();
      for (int i = 0; i < chars.length; i++) {
         char c = chars[i];
         switch (c) {
            // state1 left bracket - push current list on stack for later
            // retrieval
            // allocate new list and add it to one just pushed (remember,
            // I still have its reference).
            // Assign nlist to list
            // increment bracket count
            case '[':
               stack.push(list);
               List<Object> nlist = new ArrayList<>();
               list.add(nlist);
               list = nlist;
               bracketCount++;
               break;
            // state2 right bracket - Finished processing current sublist.
            // if previous tokens were not brackets, then add the
            // number to the list and pop off the previous one.
            // decrement bracket count
            case ']':
               if (chars[i - 1] != '[' && chars[i - 1] != ']') {
                  list.add(num);
               }
               list = stack.pop();
               bracketCount--;
               break;
            // state3 - whitespace - ignore
            case ' ':
            case '\t':
               break;
            // state4 comma - if previous token was not a right bracket,
            // then add number. Reset num for next number.
            case ',':
               if (chars[i - 1] != ']') {
                  list.add(num);
               }
               num = 0;
               break;
            // state5 digit - assumed to be a digit. Each time a digit
            // is encountered, update the number
            default:
               num = num * 10 + c - '0';
         }
         if (bracketCount < 0) {
            System.out.println("too many ] brackets at location " + i);
         }
      }
      if (bracketCount > 0) {
         System.out.println("insufficent number of ] brackets");
      }
      System.out.println(list);
   }
}

Note that in the above example, the "states" are rather "pseudo states." That is you don't need to check the current state you are in in order to determine how to process the current token or flag an error.

Answered By - WJS