I have some list of expressions,
const expressions = [
'A&(B|C)',
'A|(B&C)',
'A|(B&(C|D))',
'A|(B&C&D)',
];
Out of this, I need to get an output like,
[[A, B], [A, C]]
[[A], [B, C]]
[A, [B, C], [B, D]]
[A, [B, C, D]]
I tried to do this in the below way, But getting an empty arrays instead of 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('-------------------');
}
Output I get,
Expression: A&(B|C)
Combinations: [[]]
-------------------
Expression: A|(B&C)
Combinations: [[]]
-------------------
Expression: A|(B&(C|D))
Combinations: [[]]
-------------------
Expression: A|(B&C&D)
Combinations: [[]]
-------------------
Anyway to resolve this?
The generateCombinations function does not do anything that relates to the task. It should actually flatten the tree to two levels, where the top level is a disjuction, and the second level consists of conjunctions.
You can do this with recursion, and flatten on the way out of recursion.
I have chosen an implementation where the parser allows parentheses to be optional, in which case & gets precedence over |, and the variable names can consist of more than one character. The parser builds a binary tree. I wouldn't store variables in a separate array, but allow a child to be a variable (string) or a node.
In a second phase the tree can be converted to an array of arrays, bottom-up, where this nested array will represent either a CNF (conjunction normal form) or DNF (disjunction normal form). This representation will need to convert from one to the other to allow a node's children to be merged. This conversion is nothing else than a Cartesian product.
Finally some simplifications could be applied, so that the bottom level arrays only have unique values (so to change A&A&B to A&B). More simplification rules could be added (as can be seen in the additional test case I added), but I didn't pursue this further.
Below is a JavaScript implementation. It should not be difficult to add 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('-------------------');
}