求教Airbnb的CSV parser

这道题感觉网上没有一个正确的答案……答案要么不能处理双重"", 要么不能处理逗号在引号里面的情况，如"San Francisco, CA". 感觉找不到一个好的方法，既处理双重"", 又处理逗号在引号里面的情况。。。。

求各位大牛指点！

这类问题用“确定有限状态自动机”（DFA，Deterministic Finite Automaton）来解决是逻辑最清晰的

搜了一个blog，举的例子还算清晰，LZ可以读一读：http://helloitworks.com/754.html

然后CSV parser这个题目，我写了份参考代码，不知道是不是满足所有要求：

1. public class Main {
   
2.   public static void main(String[] args) {
   
3.     String doc =
   
4.         "John,Smith,john.smith@gmail.com,Los Angeles,1\n" +
   
5.         "Jane,Roberts,janer@msn.com,\"San Francisco, CA\",0\n" +
   
6.         "\"Alexandra \"\"Alex\"\"\",Menendez,alex.menendez@gmail.com,Miami,1\n" +
   
7.         "\"\"\"Alexandra Alex\"\"\"";
   
8. 
   
9.     System.out.println(CSVParser.Convert(doc));
   
10.   }
    
11. }
    
12. 
    
13. 
    
14. class CSVParser {
    
15.   private enum State {
    
16.     FIELD_START,
    
17.     QUOTE_LESS,
    
18.     QUOTE_START,
    
19.     QUOTE_IN_QUOTE
    
20.   }
    
21. 
    
22.   public static String Convert(String doc) {
    
23.     StringBuilder sb = new StringBuilder();
    
24.     State state = State.FIELD_START;
    
25. 
    
26.     for (int i = 0; i < doc.length(); ++i) {
    
27.       char ch = doc.charAt(i);
    
28. 
    
29.       switch (state) {
    
30.         case FIELD_START:
    
31.           if (ch == '"') {
    
32.             state = State.QUOTE_START;
    
33.             continue;
    
34.           }
    
35.           state = State.QUOTE_LESS;
    
36.           break;
    
37.         case QUOTE_LESS:
    
38.           switch (ch) {
    
39.             case ',':  ch = '|';  // fall through
    
40.             case '\n': state = State.FIELD_START; break;
    
41.             case '"':  Error(i, ch);
    
42.           }
    
43.           break;
    
44.         case QUOTE_START:
    
45.           if (ch == '"') {
    
46.             state = State.QUOTE_IN_QUOTE;
    
47.             continue;
    
48.           }
    
49.           break;
    
50.         case QUOTE_IN_QUOTE:
    
51.           switch (ch) {
    
52.             case '"': state = State.QUOTE_START; break;
    
53.             case ',': state = State.FIELD_START; ch = '|'; break;
    
54.             default:  Error(i, ch);
    
55.           }
    
56.           break;
    
57.       }
    
58.       sb.append(ch);
    
59.     }
    
60. 
    
61.     return sb.toString();
    
62.   }
    
63. 
    
64.   private static void Error(int position, char ch) {
    
65.     throw new RuntimeException(
    
66.         "Invalid character " + ch + " at position " + position);
    
67.   }
    
68. }

复制代码

magicsets 发表于 2018-1-16 02:32
我大概知道其中的问题在哪了...

一般我们考虑CSV格式，是按这个标准：https://tools.ietf.org/html/rf ...

多谢多谢！现在豁然开朗了！就是""San Francisco, CA""这个并不valid. 因为field中间的双引号只有1个，没有成对出现。

在magicsets老哥的基础上改进了一下，原本的test input最后一行1后面的\n好像是个typo.
而且这里省掉了一个状态，算是一个简化。

1. class Solution {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         String doc =
   
5.                 "John,Smith,[email]john.smith@gmail.com[/email],Los Angeles,1\n" +
   
6.                         "Jane,Roberts,[email]janer@msn.com[/email],\"San Francisco, CA\",0\n" +
   
7.                         "\"Alexandra \"\"Alex\"\"\",Menendez,[email]alex.menendez@gmail.com[/email],Miami,1 " +
   
8.                         "\"\"\"Alexandra, Alex\"\"\"";
   
9. 
   
10.         System.out.println(CSVParser.Convert(doc));
    
11.     }
    
12. 
    
13.     static class CSVParser {
    
14.         private enum State {
    
15.             FIELD_START,
    
16.             QUOTE_START,
    
17.             QUOTE_IN_QUOTE
    
18.         }
    
19. 
    
20.         public static String Convert(String doc) {
    
21.             StringBuilder sb = new StringBuilder();
    
22.             State state = State.FIELD_START;
    
23. 
    
24.             for (int i = 0; i < doc.length(); ++i) {
    
25.                 char ch = doc.charAt(i);
    
26. 
    
27.                 switch (state) {
    
28.                     case FIELD_START:
    
29.                         if (ch == '"') {
    
30.                             state = State.QUOTE_START;
    
31.                             continue;
    
32.                         } else if (ch == ',') {
    
33.                             ch = '|';
    
34.                         }
    
35.                         break;
    
36.                     case QUOTE_START:
    
37.                         if (ch == '"') {
    
38.                             state = State.QUOTE_IN_QUOTE;
    
39.                             continue;
    
40.                         }
    
41.                         break;
    
42.                     case QUOTE_IN_QUOTE:
    
43.                         switch (ch) {
    
44.                             case '"': state = State.QUOTE_START; break;
    
45.                             case ',': state = State.FIELD_START; ch = '|'; break;
    
46.                             default:  Error(i, ch);
    
47.                         }
    
48.                         break;
    
49.                 }
    
50.                 sb.append(ch);
    
51.             }
    
52. 
    
53.             return sb.toString();
    
54.         }
    
55. 
    
56.         private static void Error(int position, char ch) {
    
57.             throw new RuntimeException(
    
58.                     "Invalid character " + ch + " at position " + position);
    
59.         }
    
60.     }
    
61. }
    

复制代码

magicsets 发表于 2018-1-16 01:53
这类问题用“确定有限状态自动机”（DFA，Deterministic Finite Automaton）来解决是逻辑最清晰的

搜了 ...

多谢多谢！跑了一下你的代码，这个case仍然过不了："Jane,Roberts,janer@msn.com,\"\"San Francisco, CA\"\",0\n"
把San Francisco, CA加双引号，就过不了了。

flykite083 发表于 2018-1-16 02:01
多谢多谢！跑了一下你的代码，这个case仍然过不了："Jane,Roberts,,\"\"San Francisco, CA\"\",0\n"
把S ...

这种情况不是一个合法的输入吧

考虑下面三种情况：
(a)
"San Francisco, CA"

(b)
""San Francisco, CA""

(c)
"""San Francisco, CA"""



其中的a和c比较容易理解：

(1) a的左右双引号是用于quote里面的内容，应当去掉，所以输出就是 San Francisco, CA

(2) 对于c，考虑左边的三个双引号，第一个是用于quote后面的内容，而第二个是用于escape第三个双引号，所以只保留第三个双引号。

然后右边三个双引号也是类似处理：第四个双引号escape第五个双引号，第六个双引号与第一个双引号一起quote其中的内容，所以只保留第五个双引号。

所以输出就是 "San Francisco, CA"


那么现在问题来了，对于b，左边那两个双引号，第一个用于quote，那第二个双引号的语义是什么呢？或者说，期望的输出是什么？

flykite083 发表于 2018-1-16 02:01
多谢多谢！跑了一下你的代码，这个case仍然过不了："Jane,Roberts,,\"\"San Francisco, CA\"\",0\n"
把S ...

我大概知道其中的问题在哪了...

一般我们考虑CSV格式，是按这个标准：https://tools.ietf.org/html/rfc4180#page-2

语法部分是这样：

1. file = [header CRLF] record *(CRLF record) [CRLF]
   
2. 
   
3. header = name *(COMMA name)
   
4. 
   
5. record = field *(COMMA field)
   
6. 
   
7. name = field
   
8. 
   
9. field = (escaped / non-escaped)
   
10. 
    
11. escaped = DQUOTE *(TEXTDATA / COMMA / CR / LF / 2DQUOTE) DQUOTE
    
12. 
    
13. non-escaped = *TEXTDATA
    
14. 
    
15. COMMA = %x2C
    
16. 
    
17. CR = %x0D
    
18. 
    
19. DQUOTE =  %x22
    
20. 
    
21. LF = %x0A
    
22. 
    
23. CRLF = CR LF
    
24. 
    
25. TEXTDATA =  %x20-21 / %x23-2B / %x2D-7E

复制代码

阅读这个需要一点点编译原理的基础，不过和你的疑问相关的最重要一点是：

只有当开头有双引号时，一个field中间才可以有双引号，且必须成对出现

不满足以上要求的输入即不符合CSV格式

也就是说，类似
"abc""def"
这样的是合法的输入

类似
""abcdef""
abc""def
这样的是不合法的输入，并不满足CSV格式要求

flykite083 发表于 2018-1-16 03:03
多谢多谢！现在豁然开朗了！就是""San Francisco, CA""这个并不valid. 因为field中间的双引号只有1个，没 ...

所以对于这个invalid的输入""San Francisco,CA""是返回San Francisco|CA""（想微软的excel）打开那样，还是这个输入就不算做testcase了呢？

赞赞！面试遇到这个题目了 学习了学习了

我之前练习的时候也写过这道题，贴一下我的解法。只处理单行CSV的情况。多行的话方法类似

1. def parseCsvLine(self, line):
   
2.     fields = []
   
3.     field = ''
   
4.     inQuote = False
   
5.     i = 0
   
6. 
   
7.     while i < len(line):
   
8.         c = line[i]
   
9.         if inQuote:
   
10.             if c != '"':
    
11.                 field += c
    
12.             elif i+1 < len(line) and line[i+1] == '"':
    
13.                 field += '"'
    
14.                 i += 1
    
15.             else:
    
16.                 inQuote = False
    
17.                 fields.append(field)
    
18.                 field = ''
    
19.                 while i < len(line) and line[i] != ',':
    
20.                     i += 1
    
21.         else:
    
22.             if c == '"':
    
23.                 inQuote = True
    
24.             elif c == ',':
    
25.                 fields.append(field.strip())
    
26.                 field = ''
    
27.             elif c != ' ' or field:
    
28.                 field += c
    
29.         i += 1
    
30. 
    
31.     if field:
    
32.         fields.append(field)
    
33. 
    
34.     return '|'.join(fields)

复制代码

1. def csv_parser(list)
   
2.   list.each do |str|
   
3.     p parse(str)
   
4.   end
   
5. end
   
6. 
   
7. def parse(str)
   
8.   result = ''
   
9.   in_quote = false
   
10.   quotes = 0
    
11. 
    
12.   (0...str.size).each do |i|
    
13.     if str[i] == '"'
    
14.       quotes += 1
    
15.       if i == str.size - 1 || str[i + 1] != '"'
    
16.         result += '"' * (quotes / 2)
    
17.         in_quote = !in_quote if quotes.odd?
    
18.         quotes = 0
    
19.       end
    
20.     else
    
21.       ch = !in_quote && str[i] == ',' ? '|' : str[i]
    
22.       result += ch
    
23.     end
    
24.   end
    
25. 
    
26.   result
    
27. end
    
28. 
    
29. test = [
    
30.   'John,Smith,[email]john.smith@gmail.com[/email],Los Angeles,1',
    
31.   'Jane,Roberts,[email]janer@msn.com[/email],"San Francisco, CA",0',
    
32.   '"Alexandra, ""Alex""",Menendez,[email]alex.menendez@gmail.com[/email],Miami,1',
    
33.   '"""Alexandra Alex"""'
    
34. ]
    
35. csv_parser test

复制代码

用ruby写的，但语言选项只有python