TypeScript Algorithm for Expressions

Question

TypeScript Algorithm for Expressions

I have a list of logical expressions,

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

From these expressions, I am aiming to obtain the following output,

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

I attempted to achieve this using the code below, however, I am receiving empty arrays instead of the correct result.

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('-------------------');
}

The current output shows empty combinations for each expression. Is there any way to fix this and get the desired combinations?

typescript algorithm data-structures

Answer 1

Answer №1

The function called generateCombinations is not aligned with the task at hand. It should be structured to flatten the tree into two levels, where the top level represents a disjunction and the second level consists of conjunctions.

This can be achieved through recursive methods, working to flatten the structure as we exit recursion.

I opted for an implementation where the parser allows optional parentheses. In this setup, the & operator takes precedence over |, and variable names can contain more than one character. The parser constructs a binary tree structure. Instead of storing variables in a separate array, each child can either be a variable (string) or another node.

In a subsequent phase, the tree can be converted into an array of arrays from the bottom-up perspective. This nested array will then represent either a CNF (conjunction normal form) or DNF (disjunction normal form). To allow merging of children nodes, a conversion between the two forms needs to take place, which essentially involves a Cartesian product operation.

To simplify things further, bottom-level arrays are refined to contain only unique values (i.e., changing A&A&B to A&B). While additional simplification rules could be implemented (as evidenced by an extra test case), I have left this aspect unexplored.

Below you'll find a JavaScript implementation that can easily incorporate typing:

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="|") {
    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('-------------------');
}

Answer 2

The function called generateCombinations is not aligned with the task at hand. It should be structured to flatten the tree into two levels, where the top level represents a disjunction and the second level consists of conjunctions.

This can be achieved through recursive methods, working to flatten the structure as we exit recursion.

I opted for an implementation where the parser allows optional parentheses. In this setup, the & operator takes precedence over |, and variable names can contain more than one character. The parser constructs a binary tree structure. Instead of storing variables in a separate array, each child can either be a variable (string) or another node.

In a subsequent phase, the tree can be converted into an array of arrays from the bottom-up perspective. This nested array will then represent either a CNF (conjunction normal form) or DNF (disjunction normal form). To allow merging of children nodes, a conversion between the two forms needs to take place, which essentially involves a Cartesian product operation.

To simplify things further, bottom-level arrays are refined to contain only unique values (i.e., changing A&A&B to A&B). While additional simplification rules could be implemented (as evidenced by an extra test case), I have left this aspect unexplored.

Below you'll find a JavaScript implementation that can easily incorporate typing:

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="|") {
    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('-------------------');
}

TypeScript Algorithm for Expressions

Answer №1

Similar questions

typescript makeStyles() functions from material-ui library

What could be the reason for the tsc command not displaying compilation errors when compiling a particular file?

What steps should be taken to resolve the error message "This Expression is not constructable"?

Trying to add a single value to a specific index in a JavaScript array, but it is mistakenly assigning multiple values at once

Angular 2 iframe balked at being shown

Tips for effectively hydrating Redux state in Next.js upon page refresh?

Utilizing ES6 Promises in Mongoose with Typescript to Create a Seamless Chain

Attach an event listener to a particular textarea element

The issue with downloading all files in Firefox persists when attempting to download multiple files simultaneously due to an anchor click

What is the best way to prevent ngFor from repeating the input values being typed?

How can one retrieve the "code" attribute from a FirebaseError object in AngularFire using TypeScript?

Improving the App() function in React and Typescipt

Steps for wrapping a class with a higher order component

Guide on creating a style instance in a component class using Material-UI and Typescript

Discovering specific values for an ID using API calls in Angular (Implementing CRUD Operations in Angular with API Integration)

How to Implement Animations with Angular 2 Directives

Definition file in TypeScript for an npm package provided by an external source - constructor

Expanding the global object in ES6 modules to include TypeScript support for extensions like `Autodesk.Viewing.Extension`

Focusing in on a particular category of items based on a specific characteristic

Ionic - What is the correct way to import ViewController? - Uncaught (in promise): Error: ViewController provider not found