🐶 VO 想不太出来的一道题 请教各位

The other way to look at this problem is to see it as a binary tree. The leaf node is a single restriction. Non-leaf nodes are operators such as AND/OR. However, I have no idea on how to solve it converting to binary tree.

可以将expression分解一下再用recursion得到答案吗～分解每个expression直到成为Restriction，然后求一下是否overlap～

抛砖引玉：
首先求exp1,exp2有无重叠的部分其实就是求exp1 && exp2，把两个表达式放一起中间直接加个与，然后用开始evaluate expression tree
表达式的结果用map表示，key是变量名，value是list of interval。interval本身表示与，多个interval表示或，比如
(A>3)&&(A<6)表示成(3,6)，
(A>3)||(A<6)表示成 [3,inf],[-inf,6]
然后计算与表达式就是经典的算interval intersect，或表达式就直接加进list，可选merge interval 化简。算与的时候检查一下是否重叠部分为空即可。

把表达式变化为expA and exp

pureklkl 发表于 2021-10-16 13:21
抛砖引玉：
首先求exp1,exp2有无重叠的部分其实就是求exp1 && exp2，把两个表达式放一起中间直接加个与， ...

思路很棒！感觉很接近了。请问如果是这样的表达式：

1. (A > 1 && B < 1) OR (A < 1 && B > 1)

复制代码

那么map的内容长什么样呢？

samson1215 发表于 2021-10-17 14:15
思路很棒！感觉很接近了。请问如果是这样的表达式：那么map的内容长什么样呢？

哦，我没考虑变量之间的与或表达，只想了单变量区间的。
多变量因为相当于考虑多维问题，我考虑过kd tree但是那个只能读，不能增删改
我目前的思路：假设每个变量是一个维度，然后树的每层节点代表一维，指针代表对应的区间

你这个式子表示成

A:         [(1,inf), (inf,1)]
              |            |
B:       [(inf,1)]    [(1,inf)]
注意第一层的A是一个节点，两个区间分别对应B的两个节点。也就是A每多一个区间，就要多加一个B的节点，来表示A对应区间内B的有效范围。如过有C的话，B也同理。
两个树合并的时候，如果是或，只要把树里层数最高的节点接上就行。与会很复杂，要逐层merge。
这个复杂度会很高，因为最后一层的节点数是之前所有有效区间的累乘。

我感觉应该有专门的数据结构表示这种东西，我是不太清楚，有知道的求告知哈。

expr1 (expr2)应该默认化到比较简单了吧？比方不会出现

expr1: (foo = 'A') AND (foo != 'A')

类似情形