如何实现OR(AND)与AND(OR)逻辑语句的双向转换算法？

已知前提 #

枚举定义 #

export enum ComparisonOperators {
   MATCH_CONTAINS = 'contains',
   MATCH_DOES_NOT_CONTAIN = 'not_contains',
   MATCH_EQUALS = 'equals',
   MATCH_NOT_EQUALS = 'not_equals',
   MATCH_STARTS_WITH = 'starts_with',
   MATCH_DOES_NOT_START_WITH = 'not_starts_with',
   MATCH_ENDS_WITH = 'ends_with',
   MATCH_DOES_NOT_END_WITH = 'not_ends_with',
   MATCH_REGEX = 'matches_regex',
   DOES_NOT_MATCH_REGEX = 'not_matches_regex',
}

OR(AND) 示例结构 #

{
   nodeType: 'OR',
   children: [
     {
        nodeType: 'AND',
        children: [
            {
              operator: ComparisonOperators.MATCH_EQUALS,
              field: 'A',
              nodeType: 'LEAF',
              value: 'abc',
            },
            {
              operator: ComparisonOperators.MATCH_STARTS_WITH,
              field: 'B',
              nodeType: 'LEAF',
              value: 'rfg',
            },
        ],
     },
     {
        nodeType: 'AND',
        children: [
            {
              operator: ComparisonOperators.MATCH_DOES_NOT_END_WITH,
              field: 'C',
              nodeType: 'LEAF',
              value: 'esa',
            },
            {
              operator: ComparisonOperators.MATCH_REGEX,
              field: 'D',
              nodeType: 'LEAF',
              value: '/[0-9]{4}/.source',
            },
        ],
     },
   ],
}

对应逻辑：('A' equals 'abc' AND 'B' startsWith 'rfg') OR ('C' doesNotEndWith 'esa' AND 'D' matchRegex '/[0-9]{4}/.source')

核心转换逻辑 #

OR(AND)结构属于析取范式（DNF），要转换为AND(OR)的合取范式（CNF），核心是应用逻辑或对逻辑与的分配律——这是你已掌握的AND(OR)转OR(AND)（与对或的分配律）的对称操作：

• 与对或的分配律：A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)（对应AND(OR)转OR(AND)）
• 或对与的分配律：A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)（对应OR(AND)转AND(OR)的基础规则）

当存在多个AND子组时，需递归应用该规则，本质是生成所有跨AND组的条件组合：从每个AND组中选取一个叶子条件，将这些条件组成OR子组，最终所有OR子组通过AND连接。

实现步骤 #

1. 标准化输入：确保输入根节点为OR，所有子节点为AND，且AND的子节点均为LEAF条件（若存在嵌套更深的结构，需先扁平化处理）。
2. 生成笛卡尔积：计算所有AND组的叶子条件的笛卡尔积，每个积元素对应一个OR子组（包含来自每个AND组的一个条件）。
3. 构建AND(OR)结构：将所有生成的OR子组作为子节点，包裹在一个根AND节点下。

TypeScript 实现代码 #

export enum ComparisonOperators {
  MATCH_CONTAINS = 'contains',
  MATCH_DOES_NOT_CONTAIN = 'not_contains',
  MATCH_EQUALS = 'equals',
  MATCH_NOT_EQUALS = 'not_equals',
  MATCH_STARTS_WITH = 'starts_with',
  MATCH_DOES_NOT_START_WITH = 'not_starts_with',
  MATCH_ENDS_WITH = 'ends_with',
  MATCH_DOES_NOT_END_WITH = 'not_ends_with',
  MATCH_REGEX = 'matches_regex',
  DOES_NOT_MATCH_REGEX = 'not_matches_regex',
}

// 定义节点类型
type LeafNode = {
  nodeType: 'LEAF';
  field: string;
  operator: ComparisonOperators;
  value: string;
};

type AndNode = {
  nodeType: 'AND';
  children: LeafNode[];
};

type OrNode = {
  nodeType: 'OR';
  children: AndNode[];
};

type AndOrRootNode = {
  nodeType: 'AND';
  children: { nodeType: 'OR'; children: LeafNode[] }[];
};

// 计算多个数组的笛卡尔积（核心辅助函数）
function cartesianProduct<T>(...arrays: T[][]): T[][] {
  return arrays.reduce((acc, curr) => {
    return acc.flatMap(prev => curr.map(item => [...prev, item]));
  }, [[]] as T[][]);
}

// OR(AND) 转 AND(OR) 核心函数
function convertOrAndToAndOr(orAndRoot: OrNode): AndOrRootNode {
  // 提取所有AND组的叶子条件列表
  const andGroupLeaves = orAndRoot.children.map(group => group.children);
  
  // 生成所有跨组条件组合，每个组合对应一个OR子组
  const orGroups = cartesianProduct(...andGroupLeaves).map(conditions => ({
    nodeType: 'OR' as const,
    children: conditions
  }));
  
  // 构建根AND节点
  return {
    nodeType: 'AND',
    children: orGroups
  };
}

// 测试示例
const inputOrAnd: OrNode = {
  nodeType: 'OR',
  children: [
    {
      nodeType: 'AND',
      children: [
        { operator: ComparisonOperators.MATCH_EQUALS, field: 'A', nodeType: 'LEAF', value: 'abc' },
        { operator: ComparisonOperators.MATCH_STARTS_WITH, field: 'B', nodeType: 'LEAF', value: 'rfg' }
      ]
    },
    {
      nodeType: 'AND',
      children: [
        { operator: ComparisonOperators.MATCH_DOES_NOT_END_WITH, field: 'C', nodeType: 'LEAF', value: 'esa' },
        { operator: ComparisonOperators.MATCH_REGEX, field: 'D', nodeType: 'LEAF', value: '/[0-9]{4}/.source' }
      ]
    }
  ]
};

// 执行转换
const outputAndOr = convertOrAndToAndOr(inputOrAnd);
console.log(JSON.stringify(outputAndOr, null, 2));

转换结果验证 #

上述示例转换后的AND(OR)结构对应逻辑：
(A=abc OR C notEndsWith esa) AND (A=abc OR D matches regex) AND (B startsWith rfg OR C notEndsWith esa) AND (B startsWith rfg OR D matches regex)
该逻辑与原OR(AND)逻辑完全等价，可通过真值表或逻辑运算规则验证。

内容的提问来源于stack exchange，提问作者MChaker