Airbnb Interview - Nested Integer List Parser - 我的博客 - ITeye技术网站

Airbnb Interview - Nested Integer List Parser - 我的博客 - ITeye技术网站
实现一个mini parser, 输入是以下格式的string:"324" or"[123,456,[788,799,833],[[]],10,[]]"
要求输出:324 or [123,456,[788,799,833],[[]],10,[]].
也就是将字符串转换成对应的格式的数据.
输入一个数组的字符串, 要返回一个数组, 里面每一个元素是要么一个整数, 要么是一个数组.
但是注意数组可以多层嵌套. 

1. public class NestedIntList {  
2.   
3.     private int value;  
4.     private List<NestedIntList> intList;  
5.     private boolean isNumber;  
6.       
7.     public NestedIntList(int v) {  
8.         this.value = v;  
9.         this.isNumber = true;  
10.     }  
11.       
12.     public NestedIntList() {  
13.         this.intList = new ArrayList<>();  
14.         this.isNumber = false;  
15.     }  
16.       
17.     public void add(NestedIntList l) {  
18.         intList.add(l);  
19.     }  
20.       
21.     public static NestedIntList fromString(String s) {  
22.         if(!s.startsWith("[")) {  
23.             return new NestedIntList(Integer.parseInt(s));  
24.         }  
25.         NestedIntList result = null;  
26.         Stack<NestedIntList> stack = new Stack<>();  
27.         int i = 0, left = 1;  
28.         while(i < s.length()) {  
29.             char c = s.charAt(i);  
30.             if(c == '[') {  
31.                 NestedIntList num = new NestedIntList();  
32.                 if(!stack.isEmpty()) {  
33.                     stack.peek().add(num);  
34.                 }  
35.                 stack.push(num);  
36.                 left = i+1;  
37.             } else if(c == ',' || c == ']') {  
38.                 if(left != i) {  
39.                     int v = Integer.parseInt(s.substring(left, i));  
40.                     NestedIntList num = new NestedIntList(v);  
41.                     stack.peek().add(num);  
42.                 }  
43.                 left = i+1;  
44.                 if(c == ']') result = stack.pop();  
45.             }   
46.             i++;  
47.         }  
48.         return result;  
49.     }  
50.       
51.     public String toString() {  
52.         if(isNumber) {  
53.             return ""+value;  
54.         } else {  
55.             return intList.toString();  
56.         }  
57.     }  
58. } 

http://buttercola.blogspot.com/2015/11/airbnb-mini-parser.html

  private static class NestedIntList {

    private int value;

    private boolean isNumber;

    private List<NestedIntList> intList;

     

    // Constructor to construct a number

    public NestedIntList(int value) {

      this.value = value;

      isNumber = true;

    }

     

    // Constructor to construct a list

    public NestedIntList() {

      intList = new ArrayList<>();

      isNumber = false;

    }

     

    public void add(NestedIntList num) {

      this.intList.add(num);

    }

     

    public NestedIntList miniParser(String s) {

      if (s == null || s.length() == 0) {

        return null;

      }

       

      // Corner case "123"

      if (s.charAt(0) != '[') {

        int num = Integer.parseInt(s);

        return new NestedIntList(num);

      }

       

      int i = 0;

      int left = 1;

      Stack<NestedIntList> stack = new Stack<>();

      NestedIntList result = null;

       

      while (i < s.length()) {

        char c = s.charAt(i);

        if (c == '[') {

          NestedIntList num = new NestedIntList();

          if (!stack.isEmpty()) {

            stack.peek().add(num);

          }

          stack.push(num);

          left = i + 1;

        } else if (c == ',' || c == ']') {

          if (left != i) {

            int value = Integer.parseInt(s.substring(left, i));

            NestedIntList num = new NestedIntList(value);

            stack.peek().add(num);

          }

          left = i + 1;

           

          if (c == ']') {

            result = stack.pop();

          }

        }

         

        i++;

      }

       

      return result;

    }

     

    public String toString() {

      if (this.isNumber) {

        return this.value + "";

      } else {

        return this.intList.toString();

      }

    }

  }

}

Read full article from Airbnb Interview - Nested Integer List Parser - 我的博客 - ITeye技术网站