原题见 百姓网公开笔试题：查询条件的子集判断

    我的答卷在 http://soulogic.com/subset_test/subset_test.tar.gz

    演示地址为 http://soulogic.com/subset_test/

---

    碰到这道题时才意识到自己的见识浅薄，非等到这种题出来才能明白，高等数学对于程序员而言是多么重要。其中最难最关键的部分是在留言里看到了 qmigh 的解释才搞定的。

    这道题分三部分：把查询语句转成数组结构，然后把层级混乱的条件最终分解成 以 OR 关联的 AND 合集（也就是 qmigh 所解释的），以及按规则来读取并判断两个数组。在我的代码里，Class TreeStore 负责前两步，Class SetCheck 负责后一步。

    由于我完全说不出任何术语，只能把数组的转换过程列一下了。

    原始语句

    a = 1 AND (b = 1 OR (c = 1 AND (e > 1 OR f = 1)))

    第一步，循环用正则，从最里面的括号开始，分解出每一级。这样每一级里面都没括号了

    Array

    (

        [1] => e > 1 OR f = 1

        [2] => c = 1 AND _1

        [3] => b = 1 OR _2

        [4] => a = 1 AND _3

    )

    按照 AND OR 的优先级进一步分解

    Array

    (

        [AND] => Array

            (

                [0] => a = 1

                [1] => Array

                    (

                        [OR] => Array

                            (

                                [0] => b = 1

                                [1] => Array

                                    (

                                        [AND] => Array

                                            (

                                                [0] => c = 1

                                                [1] => Array

                                                    (

                                                        [OR] => Array

                                                            (

                                                                [0] => e > 1

                                                                [1] => f = 1

                                                            )

                                                    )

                                            )

                                    )

                            )

                    )

            )

    )

    将上述数组最终分解成 OR 下的一堆 AND

    Array

    (

        [OR] => Array

            (

                [0] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => b = 1

                            )

                    )

                [1] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => c = 1

                                [2] => e > 1

                            )

                    )

                [2] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => c = 1

                                [2] => f = 1

                            )

                    )

            )

    )

    其实就是按 qmigh 说的，做一下转换，把最开始的表达式转换为

    (a = 1 AND b = 1) OR (a = 1 AND c = 1 AND e > 1) OR (a = 1 AND c = 1 AND f = 1)

    如果只有一个表达式，可以理解为只有一个元素的 AND

    如果

    (a > 3) AND (b < 4)

    可以用数组表示为

    array(

        [0] => a > 3

        [1] => b < 4

    )

    那么

    a > 3

    可以用数组表示为

    array(

        [0] => a > 3

    )

    OR 也同理

    用来判断时的数组样子，也就是 Class TreeStore 的最终输出

    Array

    (

        [0] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [b] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

            )

        [1] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [c] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [e] => Array

                    (

                        [>] => 1

                    )

            )

        [2] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [c] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [f] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

            )

    )

    至于判断，应该不算难，按照上面的数组挨个字段判断就可以了。以及判断父集合是否有子集合没有的字段，如果有，那肯定不是子集关系了。

    写完之后一直没把握到底做的对不对，要是有类似 ACID 2 或者 Man or boy test 那样的东西就好了。如果能有人告诉我有什么复杂条件是我的代码判断不了的，实在感激不尽（当然，用 10MB 长的条件语句搞溢出不算……）

    看了看 其他人的答案，“从离散数学到编译原理”，这标题总结得不错，核心也就是这两个问题吧。我用正则来把“编译”那部分绕过去了，但从执行效率上讲是很蠢的。

    看来大家都知道画蛇添足的故事，所以都只做了满足要求（“为了简单起见，只需要实现最简单的AND, OR逻辑操作，大于，等于，小于三种比较操作就好”）的最小实现。

    如果能有 PHP 同好的题解能相互学习学习那是最好了，其他语言的看不懂 -_-

    原来还自诩为程序员，被这道题臊的不行，我现在的定义是，没法独自实现一个 C Compiler 的人充其量也不过是 coding fans。

    给自己定下了三年目标：学离散数学、学微积分、学《SICP》

    

建议继续学习：

1. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读：9042)
2. 谷歌(Google)2011年校园招聘笔试题    (阅读：8911)
3. 你是那10%可以实现二分查找算法的程序员吗？    (阅读：6508)
4. 15道使用频率极高的基础算法题    (阅读：5616)
5. 新浪微博笔试题：找出共有2个以上标签的用户对    (阅读：4969)
6. 有道实习生笔试总结    (阅读：4542)
7. 2014网易前端开发笔试题笔记    (阅读：3948)
8. 百姓网公开笔试题：查询条件的子集判断    (阅读：2573)
9. mysql数据库查询优化    (阅读：2545)
10. 百姓网公开笔试题结果展示    (阅读：2313)