Distribution over boolean expressions
Statement
Goal
You have to develop a boolean expression to obtain a disjunctive form (DF).A DF is a clauses disjunction, meaning a list of expression between parenthesis, in which there is only "AND" (clauses), all separated by "OR" (disjunction).
To obtain a DF, you can consider that you distribute the "AND" over the "OR", just like you would do in an algebraic expression when you distribute the multiplication over the addition.
For example,
(a | b) & (c | d)
gives :
(a & c) | (a & d) | (b & c) | (b & d)
Input
A string being the boolean expression.
Authorized input characters are
. Spaces : non-significant, they make the input easier to read.
. Operators "and" and "or" are respectively the characters & and |
. Lower case alphabet letters, being the variables of the expression.
Authorized input characters are
. Spaces : non-significant, they make the input easier to read.
. Operators "and" and "or" are respectively the characters & and |
. Lower case alphabet letters, being the variables of the expression.
Output
A string being an equivalent boolean expression (same table of truth), after the full development of "AND" over the "OR".
To obtain a unique solution, you'll be asked to perform the following operations on your development :
- Remove duplicated terms from clauses:
(a & a) gives a
- Remove clauses that includes another one:
(a & b) | (a & b & c) gives (a & b)
- Sort terms in clauses, and then clauses themselves, by lexicographic order:
(c & b) | (z & a) gives (a & z) | (b & c)
There must be spaces around operators.
There must be parenthesis around clauses if and only if there are strictly more than one element inside.
Valid output examples
- a | (b & c)
- (a & b)
Invalid output examples
- (a | b)
- a & c
To obtain a unique solution, you'll be asked to perform the following operations on your development :
- Remove duplicated terms from clauses:
(a & a) gives a
- Remove clauses that includes another one:
(a & b) | (a & b & c) gives (a & b)
- Sort terms in clauses, and then clauses themselves, by lexicographic order:
(c & b) | (z & a) gives (a & z) | (b & c)
There must be spaces around operators.
There must be parenthesis around clauses if and only if there are strictly more than one element inside.
Valid output examples
- a | (b & c)
- (a & b)
Invalid output examples
- (a | b)
- a & c
Constraints
Input expressions are always well-formed.
Variables are only one letter.
Variables are only one letter.
Example
Input
b & a & (c | d)
Output
(a & b & c) | (a & b & d)
Tags
Difficulty
Medium
Test cases
left development Test
Input
b & a & (c | d)
Output
(a & b & c) | (a & b & d)
left development Validator
Input
a & (c | b)
Output
(a & b) | (a & c)
just the same Test
Input
a | (b & c & d) | z
Output
a | (b & c & d) | z
just the same Validator
Input
a | (b & c)
Output
a | (b & c)
right developement Test
Input
(b | c) & a & d
Output
(a & b & d) | (a & c & d)
right developement Validator
Input
(b | c) & a
Output
(a & b) | (a & c)
all in Test
Input
((c & b & a & i) | z) | (((d | e) & f & g) & (h | i)) | (f & g & i)
Output
(a & b & c & i) | (d & f & g & h) | (e & f & g & h) | (f & g & i) | z
all in Validator
Input
((c & b & a & m) | w) | (((d | e) & f & g) & (h | m)) | (f & g & m)
Output
(a & b & c & m) | (d & f & g & h) | (e & f & g & h) | (f & g & m) | w
Solution language
Solution
Stub generator input