古狗电面跪经

第三题将文本“分开”的方法，比较系统的知识应该是在"Programming Languages and Compilers"这类课程里前几章关于"Lexer/Parser"的部分。

只是要做题目的话，可以用一个stack去hack出来（stack=递归，是处理树状结构的很好的方法）， 例如楼上提到的类似题目LeetCode 591，Discuss里给出的答案：
https://discuss.leetcode.com/topic/91300/java-solution-use-startswith-and-indexof

更通用一点的方法是写一个简单的“递归下降语法解析器”(recursive descent parser)——这个并不难写，而且可以解决几乎所有类似的题目，建议搜索并学习一下..

实践中需要解析文本的时候一般是用"parser generator"工具，比如flex+bison / JavaCC / Antlr之类的。这道题目非常适合词法和语法混合的LL(k)的parser generator，例如Antlr，语法部分几行代码就可以表达出来了。

这么早就招全职了？还能LinkeIn直接联系HR？

第三题感觉就是设计一个DOM tree解析html 文件。
class TreeNode {
   String tag;
   String text;
   List<TreeNode> children;
}

第三题 recursive descend parser

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. 
   
6. struct TreeNode {
   
7.     string tag;
   
8.     string text;
   
9.     vector<TreeNode*> children;
   
10.     TreeNode(string tag_, string text_) {
    
11.         tag = tag_;
    
12.         text = text_;
    
13.     }
    
14. };
    
15. 
    
16. TreeNode* parse(string& html, int& i) {
    
17.     if(html[i] == '[') {
    
18.         i++; // skip '['
    
19.         int j = html.find(']', i);
    
20.         string tag = html.substr(i, j-i);
    
21.         i = j + 1;
    
22.         
    
23.         int start = i;
    
24.         TreeNode* root = new TreeNode(tag, "");
    
25.         while(html.substr(i,2) != "[/") {
    
26.             auto child = parse(html, i);
    
27.             if(child) root->children.push_back(child);
    
28.         }
    
29.         root->text = html.substr(start, i-start);
    
30.         i += 2;
    
31.         i = html.find(']', i);
    
32.         i++;// skip ']'
    
33.         return root;
    
34.     }
    
35.     else {
    
36.         while(i < html.length() && html[i] != '[') i++; // scan all text content
    
37.         return nullptr;
    
38.     }
    
39. }
    
40. 
    
41. TreeNode* parseHtml(string& html) {
    
42.     TreeNode* root = new TreeNode("","");
    
43.     for(int i = 0; i < html.length(); ) {
    
44.         auto tmp = parse(html, i);
    
45.         if(tmp) root->children.push_back(tmp);
    
46.     }
    
47.     return root;
    
48. }
    
49. 
    
50. void printTree(TreeNode* root) {
    
51.     queue<TreeNode*> q;
    
52.     q.push(root);
    
53.     while(!q.empty()) {
    
54.         int qsize = q.size();
    
55.         while(qsize-- > 0) {
    
56.             auto top = q.front();
    
57.             q.pop();
    
58.             cout << "tag:" << top->tag << " text:" << top->text << "    ";
    
59.             for(auto c : top->children) q.push(c);
    
60.         }
    
61.         cout << endl;
    
62.     }
    
63. }
    
64. 
    
65. int main(int argc, const char * argv[]) {
    
66.     // insert code here...
    
67.     string html = "[text] Hello [/text] [bold]![/bold] [mark]word[/mark]";
    
68.     printTree(parseHtml(html));
    
69.     cout << endl;
    
70.     html = "[text] Hello [/text] [bold]abc[tiny] maketiny [/tiny]123[/bold] [mark]word[/mark]";
    
71.     printTree(parseHtml(html));
    
72.     return 0;
    
73. }
    

复制代码

codemonk 发表于 2017-8-24 13:32
第三题 recursive descend parser

谢谢，下次我就写出来了。

题主电面结果怎么样？

楼主有后续吗？

littlegrass 发表于 2017-8-26 09:09
楼主有后续吗？

就继续刷题，争取再面一次呗。

FightForTomo 发表于 2017-8-26 09:26
就继续刷题，争取再面一次呗。

祝楼主好运！楼主的帖子写fresh grad 为什么不等今年的秋招 急着面SETI？

littlegrass 发表于 2017-8-26 09:39
祝楼主好运！楼主的帖子写fresh grad 为什么不等今年的秋招 急着面SETI？

年少无知唉