求教一道算法题， parse json

就是给个string,按格式打印json，注意缩进和换行
http://jsonprettyprint.com/
类似这种的， 输入[1,2,3, {"id": 1, "name": "wang", "tag":[1,"home",2], "price":234}]
要求打出来这个
[  
   1,  
   2,  
   3,  
  {   
     "id": 1,   
     "name": "wang",   
     "tag": [      1,      "home",      2    ],   
     "price": 234
   }
]

pinkdatura 发表于 2016-8-24 04:43
我的做法是iterative的，可是面试还是fail了，脸家店面，所以求教

代码基本意思有了，不过略微繁琐了些，而且某些地方和jsonprettyprint.com的结果有点出入。比如你的代码里{和[前都有换行，而jsonprettyprint中则是没有的。观察jsonprettyprint能推出真正导致换行的只有两种情况：1. {[,之后；2. ]}之前。另外的规则是1. {的下一行indent比本行增加; 2. }所在的那一行indent比上一行减少。3. 只有在换行出现以后才输出indent的空格。
只要把上面这些情况综合在一起即可。我大概写了些，交流一下。

1.   public static void prettyJSON(String s) {
   
2.     int indent=0;
   
3.     boolean lastLineBreak = false; // If the last char results in linebreak
   
4.     for (int i = 0; i < s.length(); i++) {
   
5.       boolean isEnd = (s.charAt(i)==']' || s.charAt(i)=='}');
   
6.       boolean isBegin = (s.charAt(i)=='[' || s.charAt(i)=='{');
   
7.       boolean isComma = s.charAt(i)==',';
   
8.       
   
9.       if (isEnd) {  // ] } should always be preceded by linebreak
   
10.         indent-=2;  // This line should have less indent.
    
11.         System.out.println();
    
12.         lastLineBreak = true;
    
13.       }
    
14.       if (lastLineBreak == true) { // If a new line begins, indent it.
    
15.         if (s.charAt(i)==' ') continue;     // Skip spaces              
    
16.         for (int j = 0; j < indent; ++j) System.out.print(" ");
    
17.       }
    
18. 
    
19.       if (isBegin) { // For [ and {, next line has more indent.
    
20.         indent += 2;
    
21.       }
    
22.       lastLineBreak = isBegin || isComma; // Only [{, results in linebreak
    
23.       System.out.print(s.charAt(i));
    
24.       if (lastLineBreak) System.out.println();
    
25.     }
    
26.   }

复制代码

西子 发表于 2017-1-1 14:58
太赞了！！！

请问大神：处理这类问题一般如何着手呢？我碰到parse JSON/CSV这类的，一直比较蒙。。

我的想法还是用类似用元胞状态机的思路，即每遇到一个字符，根据当前系统的状态，如何改变系统的状态？
观察楼主给的例子，能总结出下面的规律：

1. 遇到[和{时，一定会换行，并且缩进+2
2. 遇到}和]时，一定会换行，并且缩进-2
3. 遇到,时，或者下一个元素是}或]，一定会换行，并且下一行缩进不变。
4. 遇到空格，换行符等全部忽略（因为规则123已经让我们自己在适当的地方加入换行符了）。
5. 除上述4条以外，全部字符都原样打印（为求美观，:号后可以多打印一个空格）。

所以看起来好像很麻烦，其实只要掌握5条简单规则就能够做到完美的PrettyJSON了。

这个题在interviewbit上有，我的解法，python的，在原题基础上有简化，因为原题有些corner case没什么意思。比如说我假设一定是 {a,b,c,} 这样的输入，而不是{a,b,c}。处理后者也很简单，但是会让代码结构不清晰，因此我去掉了：

1. def prettyJSON(self, A):
   
2.     r = []
   
3.     t = ""
   
4.     d = 0
   
5.     for i in xrange(len(A)):
   
6.         x = A[i]
   
7.         if x in "[{":
   
8.             r.append("\t"*d + x)
   
9.             d += 1
   
10.         elif x in "]}":
    
11.             d -= 1
    
12.             r.append("\t"*d + x)
    
13.         elif x == ",":
    
14.             r.append("\t"*d + t + ",")
    
15.             t = ""
    
16.         elif x == ":":
    
17.             t += x
    
18.             if A[i + 1] in "[{":
    
19.                 r.append("\t"*d + t)
    
20.                 t = ""
    
21.         else:
    
22.             t += x
    
23.     return r

复制代码

我的做法是iterative的，可是面试还是fail了，脸家店面，所以求教

1. public static void main(String [] args) {
   
2.       String s = "[1,2,3, {\"id\": 1, \"name\": \"wang\", \"tag\":[1,\"home\",2], \"price\":234}]";
   
3.      String ss = "{ \"firstName\": \"John\", \"lastName\": \"Smith\", \"isAlive\": true, \"age\": 25, \"address\": { \"streetAddress\": \"21 2nd Street\", \"city\": \"New York\", \"state\": \"NY\", \"postalCode\": \"10021-3100\" }, \"phoneNumbers\": [ { \"type\": \"home\", \"number\": \"212 555-1234\" }, { \"type\": \"office\", \"number\": \"646 555-4567\" }, { \"type\": \"mobile\", \"number\": \"123 456-7890\" } ], \"children\": [], \"spouse\": nul }";
   
4. 
   
5. 
   
6.      parseJson(ss);
   
7.    
   
8.   }
   
9.   
   
10.   public static String dentSpace(int dentNum) {
    
11.       int count = 0;
    
12.       StringBuilder sb = new StringBuilder();
    
13.         while(count < dentNum){
    
14.           sb.append(" ");
    
15.           count++;
    
16.         }
    
17.       return sb.toString();
    
18. 
    
19.   }
    
20.   
    
21.   public static void parseJson(String s) {
    
22.       int dent = 0;
    
23.       for(int i = 0; i < s.length(); i++) {
    
24.            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
    
25.              StringBuilder sb = new StringBuilder();
    
26.              while(i < s.length() && (s.charAt(i) >= '0' && s.charAt(i) <= '9' || s.charAt(i) == '.')){
    
27.                  sb.append(s.charAt(i));
    
28.                  i++;
    
29.              }
    
30.              String dents = dentSpace(dent);
    
31.              System.out.print(dents + sb.toString());
    
32.              i--;
    
33.            }else if(s.charAt(i) == '[' || s.charAt(i) == '{'){
    
34.                if(i != 0 && s.charAt(i-1) == ':'){
    
35.                    dent++;
    
36.                    System.out.print(s.charAt(i));
    
37.                    continue;
    
38.                }
    
39. 
    
40.             
    
41.             
    
42.              String dents = dentSpace(dent);
    
43.              dent++;
    
44.              System.out.print("\n" + dents + s.charAt(i)+"\n");
    
45.             
    
46.            }else if (s.charAt(i) == ','){     
    
47. 
    
48.                System.out.print(s.charAt(i) + "\n");
    
49.            }else if(s.charAt(i) == ']' || s.charAt(i) == '}') {
    
50.               dent--;
    
51.               String dents = dentSpace(dent);
    
52.               if(i < s.length()-1 && s.charAt(i+1) == ',' ){
    
53.                  System.out.println("\n" + dents + s.charAt(i) + ",");
    
54.                  i++;
    
55.               }else{
    
56.                  System.out.println("\n" + dents + s.charAt(i));
    
57.               }
    
58.               
    
59.            }else if(s.charAt(i) == '\"' ){ // new string key
    
60.                StringBuilder sb2 = new StringBuilder();
    
61.                sb2.append(s.charAt(i));
    
62.                i++;
    
63.                while(i < s.length() && s.charAt(i) != '\"'){
    
64.                   sb2.append(s.charAt(i));
    
65.                   i++;
    
66.                }
    
67.                sb2.append(s.charAt(i));
    
68.                String dents = dentSpace(dent);
    
69.                System.out.print(dents + sb2.toString());         
    
70.            }else if(s.charAt(i) == ':'){
    
71.                 System.out.print(s.charAt(i));
    
72.            }
    
73. 
    
74.         
    
75.       }  

复制代码

stellari 发表于 2016-8-24 15:37
代码基本意思有了，不过略微繁琐了些，而且某些地方和jsonprettyprint.com的结果有点出入。比如你的代码 ...

现在才看到，原来是leetcode大牛～感谢谢感谢～

又写了个recursion版本的，很丑，求stellari大神还有各位大牛指教～，遇到这种题真心觉得郁闷， 明明做了fb这2年多的所有店面题，可遇到新题，又fail了，求各位战友们的学习／刷题建议～

1. public class JsonParser {
   
2. 
   
3.     boolean isInBracket(String str, int ind){
   
4.         int leftBracket = 0;
   
5.         int rightBracket = 0;
   
6.         int leftCurlyBracket = 0;
   
7.         int rightCurlyBracket = 0;
   
8.         for(int i=1;i<ind;i++){
   
9.             if (str.charAt(i)=='{'){
   
10.             leftCurlyBracket++;
    
11.             }
    
12.             if (str.charAt(i)=='}'){
    
13.             rightCurlyBracket++;
    
14.             }
    
15.             if (str.charAt(i)=='['){
    
16.             leftBracket++;
    
17.             }
    
18.             if (str.charAt(i)==']'){
    
19.             rightBracket++;
    
20.             }
    
21.         }
    
22.         if(str.charAt(ind)==','){
    
23.             if (leftBracket>rightBracket||leftCurlyBracket>rightCurlyBracket){
    
24.             return true;
    
25.             }
    
26.         }
    
27.         return false;
    
28.     }
    
29.     boolean containsJsonObj(String line){
    
30.     int i=0;
    
31.     for(i=0;i<line.length();i++){
    
32.         if(line.charAt(i)==':'){
    
33.         break;
    
34.         }
    
35.     }
    
36.     while(i<line.length()-1&&line.charAt(i+1)==' '){
    
37.         i++;
    
38.     }
    
39.     if(i<line.length()-1){
    
40.         if(line.charAt(i+1)=='['||line.charAt(i+1)=='{'){
    
41.         return true;
    
42.         }
    
43.     }
    
44.     return false;
    
45.     }
    
46.     char firstBracket(String line){
    
47.     for(int i=0;i<line.length();i++){
    
48.         if(line.charAt(i)=='['||line.charAt(i)=='{'){
    
49.         return line.charAt(i);
    
50.         }
    
51.     }
    
52.     return 'X';
    
53.     }
    
54.     char lastBracket(String line){
    
55.         for(int i=line.length()-1;i>=0;i--){
    
56.             if(line.charAt(i)==']'||line.charAt(i)=='}'){
    
57.             return line.charAt(i);
    
58.             }
    
59.         }
    
60.         return 'X';
    
61.     }
    
62.     public List<String> split(String line, int level){
    
63.         List<Integer> splitInd = new ArrayList<Integer>();
    
64.         splitInd.add(0);
    
65.         for(int i=1;i<line.length()-1;i++){
    
66.             if(line.charAt(i)==','){
    
67.                 if(isInBracket(line,i)){
    
68.                     
    
69.                 }else{
    
70.                     splitInd.add(i);
    
71.                 }
    
72.             }
    
73.         }
    
74.         splitInd.add(line.length()-1);
    
75.         for(int i=0;i<splitInd.size()-1;i++){
    
76.             String section = line.substring(splitInd.get(i)+1,splitInd.get(i+1));
    
77.             for(int j=0;j<level;j++){
    
78.             System.out.print("\t");
    
79.             }
    
80.             if (containsJsonObj(section)){
    
81.             String array[]=section.split(":",2);
    
82.             System.out.println(array[0]+":"+firstBracket(array[1]));
    
83.             split(array[1],level+1);
    
84.             }else{
    
85.             System.out.println(section);
    
86.             }
    
87.             if (lastBracket(section)!='X'){
    
88.             for(int j=0;j<level;j++){
    
89.                 System.out.print("\t");
    
90.             }
    
91.             System.out.println(lastBracket(section));
    
92.             }
    
93.         }
    
94.         return new ArrayList<String>();
    
95.     }
    
96.     public void print(String json){
    
97.     List<String> lines = split(json,0);
    
98.         for(int i=0;i<lines.size();i++){
    
99.             System.out.println(lines.get(i));
    
100.         }
     
101.     }
     
102. 
     
103.     public static void main(String args[]){
     
104.     JsonParser j = new JsonParser();
     
105.     String line =
     
106. "{\"hello\":\"world\",\"key1\":20,\"key2\":20.3,\"foo\":{\"hello1\":\"world1\",\"hello5\":500,\"key3\":[150,200,300,\"hello\"],\"key4\":{\"hello1\":\"world1\",\"key3\":[200,300]}}}";
     
107.     String ss = "{ \"firstName\": \"John\", \"lastName\": \"Smith\", \"isAlive\": true, \"age\": 25, \"address\": { \"streetAddress\": \"21 2nd Street\", \"city\": \"New York\", \"state\": \"NY\", \"postalCode\": \"10021-3100\" }, \"phoneNumbers\": [ { \"type\": \"home\", \"number\": \"212 555-1234\" }, { \"type\": \"office\", \"number\": \"646 555-4567\" }, { \"type\": \"mobile\", \"number\": \"123 456-7890\" } ], \"children\": [], \"spouse\": nul }";
     
108.     j.print(ss);
     
109. 
     
110.     }
     
111. 
     
112. }

复制代码

stellari 发表于 2016-8-24 15:37
代码基本意思有了，不过略微繁琐了些，而且某些地方和jsonprettyprint.com的结果有点出入。比如你的代码 ...

太赞了！！！

请问大神：处理这类问题一般如何着手呢？我碰到parse JSON/CSV这类的，一直比较蒙。。

谢谢！

stellari 发表于 2017-1-2 15:54
我的想法还是用类似用元胞状态机的思路，即每遇到一个字符，根据当前系统的状态，如何改变系统的状态？
...

谢谢！！我对照代码，再好好琢磨琢磨，新年快乐！

以下Java代码是根据2楼整理的：
[输出结果跟jsonprettyprint.com 保持一致]

1. 
   
2.     public void prettyJSON(String str){
   
3.         int indent = 0;
   
4.         for(int i = 0; i < str.length(); i++){
   
5.             char s = str.charAt(i);
   
6.             if("[{,".indexOf(s) >= 0){
   
7.                 System.out.print(s + "\n");
   
8.                 if(s != ',') indent ++;
   
9.                 for(int j = 0; j<indent; j++){
   
10.                     System.out.print("  ");
    
11.                 }
    
12.             }
    
13.             else if("}]".indexOf(s) >= 0){
    
14.                 System.out.println();
    
15.                 indent --;
    
16.                 for(int j = 0; j<indent; j++){
    
17.                     System.out.print("  ");
    
18.                 }
    
19.                 System.out.print(s);
    
20.             }
    
21.             else if( s != ' '){
    
22.                 System.out.print(s);
    
23.             }
    
24.         }
    
25.     }
    

复制代码