TypeScript表达式解析算法问题：生成组合为空数组的修复方案

问题说明 #

有一组布尔表达式：

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]] 

但现有TypeScript代码运行后输出全是空数组，需要修复代码实现正确转换。

原代码的问题分析 #

• 解析器逻辑缺陷：处理&/|时未正确区分运算符左右的表达式关联，比如A&(B|C)中的A和子表达式(B|C)无法建立正确层级；连续多运算符（如B&C&D）无法构建链式结构，导致子表达式层级错误。
• 组合生成逻辑错误：未区分&（与）和|（或）的不同规则，且忽略了表达式自身的变量，直接丢失了顶级节点内容。

修正后的代码 #

步骤1：修复表达式解析器 #

重新设计解析逻辑，正确处理运算符和表达式的层级关系，支持连续多运算符的链式结构：

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

    constructor(operator: string | null = null) {
        this.operator = operator;
        this.left = null;
        this.right = null;
        this.variables = [];
    }
}

function parseExpression(expression: string): ParsedExpression {
    const stack: ParsedExpression[] = [];
    let currentExpr: ParsedExpression = new ParsedExpression();

    for (const char of expression) {
        if (char === '(') {
            stack.push(currentExpr);
            currentExpr = new ParsedExpression();
        } else if (char === ')') {
            if (stack.length === 0) throw new Error("Mismatched parentheses");
            const parentExpr = stack.pop()!;
            if (parentExpr.operator) {
                parentExpr.right = currentExpr;
            } else {
                currentExpr = parentExpr;
            }
        } else if (char === '&' || char === '|') {
            const newExpr = new ParsedExpression(char);
            newExpr.left = currentExpr;
            currentExpr = newExpr;
        } else { // 处理变量
            const varExpr = new ParsedExpression();
            varExpr.variables.push(char);
            if (currentExpr.operator && !currentExpr.right) {
                currentExpr.right = varExpr;
            } else {
                currentExpr = varExpr;
            }
        }
    }

    while (stack.length > 0) {
        const parentExpr = stack.pop()!;
        parentExpr.right = currentExpr;
        currentExpr = parentExpr;
    }

    return currentExpr;
}

步骤2：修复组合生成逻辑 #

根据运算符类型（&/|）处理不同的组合规则，并正确整合变量：

function generateCombinations(parsedExpr: ParsedExpression): any[] {
    // 处理纯变量节点
    if (!parsedExpr.operator && parsedExpr.variables.length > 0) {
        return [parsedExpr.variables];
    }

    if (!parsedExpr.operator) {
        return [];
    }

    const leftCombos = parsedExpr.left ? generateCombinations(parsedExpr.left) : [];
    const rightCombos = parsedExpr.right ? generateCombinations(parsedExpr.right) : [];

    if (parsedExpr.operator === '&') {
        // &运算符：将左右组合两两合并
        const result: any[] = [];
        for (const left of leftCombos) {
            for (const right of rightCombos) {
                if (Array.isArray(left) && Array.isArray(right)) {
                    result.push(left.concat(right));
                }
            }
        }
        return result.length > 0 ? result : [];
    } else if (parsedExpr.operator === '|') {
        // |运算符：将左右组合直接合并为独立项
        return [...leftCombos, ...rightCombos];
    }

    return [];
}

完整测试代码 #

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: [["A","B"],["A","C"]]
-------------------
Expression: A|(B&C)
Combinations: [["A"],["B","C"]]
-------------------
Expression: A|(B&(C|D))
Combinations: [["A"],["B","C"],["B","D"]]
-------------------
Expression: A|(B&C&D)
Combinations: [["A"],["B","C","D"]]
-------------------

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