algorithm - 检查数值约束表达式的允许值的等价性/子集

Question

我有一个代表如下表达式的 AST:

• (<=10 && >=3) || ==0
• ==1 || ==2 || ==3
• ==1 && !=1

有数字以及 bool 运算符( || 、 && )和数字运算符( < 、 <= 、 == 、 != 、 >= 、 > )。 bool 值 not如果需要，可以将运算符添加到 AST。这些表达式用于限制可能的数字输入值(请注意，最后一个不允许任何值)。

我正在寻找一种比较两个表达式的方法。我需要知道它们是否允许完全相同的一组数字(等效)，或者一个表达式是否允许另一个表达式的子集。

Answer 1

你可以写一个函数

evaluate :: Expression -> ValueSet

将表达式计算为一组值为真的值。这个值集可能类似于

data Value = MinusInfinity | Finite Integer | PositiveInfinity
type Range = (Value, Value)
type ValueSet = [Range]

其中ValueSet是封闭的、不相交范围的排序列表。然后，您可以使用类似于排序合并的逻辑来一一实现评估的情况。