TypeScript 中的表达式算法

Question

我有一些表达式列表，

const expressions = [
    'A&(B|C)',
    'A|(B&C)',
    'A|(B&(C|D))',
    'A|(B&C&D)',
];

由此，我需要得到类似的输出，

[[A, B], [A, C]]
[[A], [B, C]]
[A, [B, C], [B, D]]
[A, [B, C, D]] 

我尝试通过以下方式执行此操作，但得到空数组而不是正确的结果。

class ParsedExpression {
    operator: string | null;
    variables: string[];
    subExpressions: ParsedExpression[];

    constructor(operator: string | null, variables: string[], subExpressions: ParsedExpression[]) {
        this.operator = operator;
        this.variables = variables;
        this.subExpressions = subExpressions;
    }
}

function parseExpression(expression: string): ParsedExpression {
    const stack: ParsedExpression[] = [];
    let currentExpr: ParsedExpression | null = null;
    let currentVariable = '';

    for (const char of expression) {
        if (char === '(') {
            if (currentExpr !== null) {
                stack.push(currentExpr);
            }
            currentExpr = null;
        } else if (char === ')') {
            if (stack.length > 0) {
                const prevExpr = stack.pop();
                if (prevExpr !== null && currentExpr !== null) {
                    prevExpr.subExpressions.push(currentExpr);
                    currentExpr = prevExpr;
                }
            }
        } else if (char === '&' || char === '|') {
            if (currentExpr === null) {
                currentExpr = new ParsedExpression(char, [], []);
            } else {
                currentExpr.operator = char;
            }
        } else {
            if (currentExpr === null) {
                currentExpr = new ParsedExpression(null, [], []);
            }
            currentExpr.variables.push(char);
        }
    }

    return currentExpr as ParsedExpression;
}

function generateCombinations(parsedExpr: ParsedExpression): string[][] {
    if (!parsedExpr.operator) {
        return [parsedExpr.variables];
    }

    const leftCombinations = parsedExpr.subExpressions.length > 0 ? generateCombinations(parsedExpr.subExpressions[0]) : [[]];
    const rightCombinations = parsedExpr.subExpressions.length > 1 ? generateCombinations(parsedExpr.subExpressions[1]) : [[]];

    const combinations: string[][] = [];
    for (const left of leftCombinations) {
        for (const right of rightCombinations) {
            combinations.push(left.concat(right));
        }
    }

    return combinations;
}

const expressions = [
    'A&(B|C)',
    'A|(B&C)',
    'A|(B&(C|D))',
    'A|(B&C&D)',
];

for (const expr of expressions) {
    const parsedExpression = parseExpression(expr);
    const combinations = generateCombinations(parsedExpression);
    console.log(`Expression: ${expr}`);
    console.log(`Combinations: ${JSON.stringify(combinations)}`);
    console.log('-------------------');
}

我得到的输出，

Expression: A&(B|C)
Combinations: [[]]
-------------------
Expression: A|(B&C)
Combinations: [[]]
-------------------
Expression: A|(B&(C|D))
Combinations: [[]]
-------------------
Expression: A|(B&C&D)
Combinations: [[]]
-------------------

有办法解决这个问题吗？

Answer 1

generateCombinations

函数不执行任何与任务相关的操作。它实际上应该将树展平为两层，其中顶层是析取，第二层由连词组成。

您可以通过递归来做到这一点，并在退出递归的过程中展平。

我选择了一种实现，其中解析器允许括号是可选的，在这种情况下，

&

优先于

|

，并且变量名称可以包含多个字符。解析器构建一棵二叉树。我不会将变量存储在单独的数组中，但允许子级作为变量（字符串）或节点。

在第二阶段，树可以自下而上地转换为数组的数组，其中该嵌套数组将表示 CNF（合取范式）或 DNF（析取范式）。该表示形式需要从一种表示形式转换为另一种表示形式，以允许合并节点的子节点。这种转换无非是笛卡尔积。

最后可以应用一些简化，以便底层数组仅具有唯一值（因此将 A&A&B 更改为 A&B）。可以添加更多简化规则（如我添加的附加测试用例中所示），但我没有进一步追求这一点。

下面是一个 JavaScript 实现。添加打字应该不难：

class BinaryNode {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function parseToBinaryTree(expression) {
    const precedence = { "&": 2, "|": 1, "(": -1, ")": 0, "": 0 };
    const operators = [];
    const operands = [];
    for (const token of expression.match(/[^&|()\s]+|\S?/gs)) {
        if (token in precedence) {
            if (token !== "(") {
                while (precedence[operators.at(-1)] >= precedence[token]) {
                    if (operands.length < 2) throw new Error("Parser: Syntax error: operands length < 2"); 
                    operands.push(new BinaryNode(operators.pop(), ...operands.splice(-2)));
                }
            }
            if (token && token !== ")") operators.push(token);
            else operators.pop(); // "("
        } else {
            operands.push(token);
        }
    }
    if (operands.length != 1) throw new Error("Parser: Syntax error: left over");
    return operands.pop();
}

const unique = values => [...new Set(values)];
const uniqueEach = arrays => arrays.map(unique);
const unwrapSingle = values => values.length === 1 ? values[0] : values;
const unwrapSingleEach = arrays => arrays.map(unwrapSingle);

function product(arrays) {
    if (arrays.length === 0) {
        return [[]];
    }
    const result = [];
    for (const x of arrays[0]) {
        for (const rest of product(arrays.slice(1))) {
            result.push([x, ...rest]);
        }
    }
    return result;
}

function normalize(root, operator="|", tab="") {
    if (typeof root === "string") { // Leaf node
        return [[root]];
    }
    const terms = uniqueEach([
        ...normalize(root.left, root.value),
        ...normalize(root.right, root.value)
    ]);
    if (root.value !== operator) {
        return uniqueEach(product(terms));
    }
    return terms;
}

const expressions = [
    'A&(B|C)',
    'A|(B&C)',
    'A|(B&(C|D))',
    'A|(B&C&D)',
    'A&(B|C)&(C|D)',
];

for (const expr of expressions) {
    const root = parseToBinaryTree(expr);
    const disj = unwrapSingleEach(normalize(root));
    console.log(`Expression: ${expr}`);
    console.log(JSON.stringify(disj));
    console.log('-------------------');
}