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 是封闭的、不相交的范围的排序列表。然后，您可以使用类似于排序合并的逻辑一个一个地实现 evaluate 的情况。