《百姓网公开笔试题：查询条件的子集判断》的一份 PHP 答卷
作者：郑凯
原题见 [url=http://home.wangjianshuo.com/cn/20100505_ccceeieeaece.htm]百姓网公开笔试题：查询条件的子集判断[/url]
我的答卷在 [url]http://soulogic.com/subset_test/subset_test.tar.gz[/url]
演示地址为 [url]http://soulogic.com/subset_test/[/url]
[hr]
碰到这道题时才意识到自己的见识浅薄，非等到这种题出来才能明白，高等数学对于程序员而言是多么重要。其中最难最关键的部分是在留言里看到了 [url=http://qmigh.blogspot.com/2010/05/blog500-querybuilderqueryandor-tyler.html]qmigh[/url] 的解释才搞定的。
这道题分三部分：把查询语句转成数组结构，然后把层级混乱的条件最终分解成 以 OR 关联的 AND 合集（也就是 qmigh 所解释的），以及按规则来读取并判断两个数组。在我的代码里，Class TreeStore 负责前两步，Class SetCheck 负责后一步。
由于我完全说不出任何术语，只能把数组的转换过程列一下了。
原始语句
[code]
a = 1 AND (b = 1 OR (c = 1 AND (e > 1 OR f = 1)))
[/code]
第一步，循环用正则，从最里面的括号开始，分解出每一级。这样每一级里面都没括号了
[code]
Array
(
[1] => e > 1 OR f = 1
[2] => c = 1 AND _1
[3] => b = 1 OR _2
[4] => a = 1 AND _3
)
[/code]
按照 AND OR 的优先级进一步分解
[code]
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
)
)
)
)
)
)
)
)
[/code]
将上述数组最终分解成 OR 下的一堆 AND
[code]
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
)
)
)
)
[/code]
其实就是按 qmigh 说的，做一下转换，把最开始的表达式转换为
[code]
(a = 1 AND b = 1) OR (a = 1 AND c = 1 AND e > 1) OR (a = 1 AND c = 1 AND f = 1)
[/code]
如果只有一个表达式，可以理解为只有一个元素的 AND
如果
[code]
(a > 3) AND (b < 4)
[/code]
可以用数组表示为
[code]
array(
[0] => a > 3
[1] => b < 4
)
[/code]
那么
[code]
a > 3
[/code]
可以用数组表示为
[code]
array(
[0] => a > 3
)
[/code]
OR 也同理
用来判断时的数组样子，也就是 Class TreeStore 的最终输出
[code]
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
)
)
)
)
[/code]
至于判断，应该不算难，按照上面的数组挨个字段判断就可以了。以及判断父集合是否有子集合没有的字段，如果有，那肯定不是子集关系了。
写完之后一直没把握到底做的对不对，要是有类似 [url=http://www.webstandards.org/files/acid2/test.html]ACID 2[/url] 或者 [url=http://en.wikipedia.org/wiki/Man_or_boy_test]Man or boy test[/url] 那样的东西就好了。如果能有人告诉我有什么复杂条件是我的代码判断不了的，实在感激不尽（当然，用 10MB 长的条件语句搞溢出不算……）
看了看 [url=http://home.wangjianshuo.com/cn/20100511_ccceecc.htm]其他人的答案[/url]，“从离散数学到编译原理”，这标题总结得不错，核心也就是这两个问题吧。我用正则来把“编译”那部分绕过去了，但从执行效率上讲是很蠢的。
看来大家都知道画蛇添足的故事，所以都只做了满足要求（“为了简单起见，只需要实现最简单的AND, OR逻辑操作，大于，等于，小于三种比较操作就好”）的最小实现。
如果能有 PHP 同好的题解能相互学习学习那是最好了，其他语言的看不懂 -_-
原来还自诩为程序员，被这道题臊的不行，我现在的定义是，没法独自实现一个 C Compiler 的人充其量也不过是 coding fans。
给自己定下了三年目标：学离散数学、学微积分、学[url=http://book.douban.com/subject/1148282/]《SICP》[/url]